Nested Weight Constraints in ASP

• Autorzy: Costantini, S. , Formisano, A.
• Języki publikacji: EN

Abstrakty

EN

Weight constraints are a powerful programming construct that has proved very useful within the Answer Set Programming paradigm. In this paper, we argue that practical Answer Set Programming might take profit from introducing some forms of nested weight constraints. We define such empowered constraints (that we call 'Nested Weight Constraints') and discuss their semantics and their complexity.

Słowa kluczowe

EN

knowledge representation; non-monotonic reasoning; weight constraints in ASP

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 124, nr 4
• Strony: 449--464
• Opis fizyczny: Bibliogr. 31 poz.

Twórcy

autor

Costantini, S.

• DISIM - Universita degli Studi di L'Aquila, Via Vetoio Loc. Coppito, I-67100 L'Aquila, Italy,

autor

Formisano, A.

• Dipartimento di Matematica e Informatica, Universita di Perugia, via Vanvitelli 1, I-06123, Perugia, Italy,

Bibliografia

• [1] M. Alviano, F. Calimeri, W. Faber, S. Perri, and N. Leone. Unfounded sets and well-founded semantics of answer set programs with aggregates. J. of Artificial Intelligence Research, 42:487-527, 2011.
• [2] T. Asikainen, T. Mannisto, V. Myllarniemi, and T. Soininen. Kumbang configurator - a configuration tool for software product families. In In Proc. ofIJCAI05 Workshop on Configuration, 2005.
• [3] C. Baral. Knowledge representation, reasoning and declarative problem solving. Cambridge University Press, 2003.
• [4] G. Brewka. Answer sets and qualitative decision making. Synthese, 146(1-2):171-187, 2003.
• [5] S. Costantini and A. Formisano. Modeling preferences and conditional preferences on resource consumption and production in ASP. J. of Algorithms in Cognition, Informatics and Logic, 64(1), 2009.
• [6] S. Costantini and A. Formisano. Answer set programming with resources. J. of Logic and Computation, 20(2):533-571, 2010.
• [7] S. Costantini and A. Formisano. Augmenting weight constraints with complex preferences. In AAAI Spring Symposium: Logical Formalizations of Commonsense Reasoning. AAAI, 2011.
• [8] S. Costantini and A. Formisano. Weight constraints with preferences in ASP. In Proc. of LPNMR’11, vol. 6645 of LNCS, pp. 229-235. Springer, 2011.
• [9] S. Costantini, A. Formisano, and D. Pearce. Strong equivalence of rasp programs. In E. Erdem, J. Lee, Y. Lierler, and D. Pearce, eds., Correct Reasoning, vol. 7265 of LNCS, pp. 149-163. Springer, 2012.
• [10] S. Costantini, A. Formisano, andD. Petturiti. Extending and implementing RASP. Fundamenta Informaticae, 105(1-2):1-33, 2010.
• [11] E. Dantsin, T. Eiter, G. Gottlob, and A. Voronkov. Complexity and expressive power of logic programming. ACM Computing Surveys, 33(3):374-425, 2001.
• [12] M. Denecker and B. De Cat. DPLL(Agg): An efficient SMT module for aggregates. In Logic and Search, FLOC’10 workshop, July 2010.
• [13] A. Dovier, A. Formisano, and E. Pontelli. A comparison of CLP(FD) and ASP solutions to NP-complete problems. In M. Gabbrielli and G. Gupta, eds., Proc. ofICLP’05, vol. 3668 of LNCS, pp. 67-82. Springer, 2005.
• [14] A. Dovier, A. Formisano, and E. Pontelli. An empirical study of constraint logic programming and answer set programming solutions of combinatorial problems. J. of Experimental and Theoretical Artificial Intelligence, 21(2):79-121, 2009.
• [15] W. Faber, N. Leone, and G. Pfeifer. Semantics and complexity of recursive aggregates in answer set programming. Artificial Intelligence, 175(1):278-298, 2011.
• [16] P. Ferraris and V. Lifschitz. Weight constraints as nested expressions. TPLP, 5:45-74, 2005.
• [17] M. Gelfond. Answer sets. In Handbook of Knowledge Representation, chapter 7. Elsevier, 2007.
• [18] M. Gelfond and V. Lifschitz. The stable model semantics for logic programming. In R. Kowalski and K. Bowen, eds., Proc. ofICLP/SLP, pp. 1070-1080. The MIT Press, 1988.
• [19] N. Leone. Logic programming and nonmonotonic reasoning: From theory to systems and applications. In C. Baral, G. Brewka, and J. Schlipf, eds., Proc. ofLPNMR’07, vol. 4483 of LNCS. Springer, 2007.
• [20] N. Leone, G. Pfeifer, W. Faber, T. Eiter, G. Gottlob, S. Perri, and F. Scarcello. The DLV system for knowledge representation and reasoning. ACM TOCL, 7(3):499-562, 2006.
• [21] V. Lifschitz. Answer set planning. In D. De Schreye, ed., Proc. ofICLP’99, pp. 23-37. The MIT Press, 1999.
• [22] V. Lifschitz, D. Pearce, and A. Valverde. Strongly equivalent logic programs. ACM TOCL, 2:526-541, 2001.
• [23] J. McCarthy. Elaboration tolerance. In Proc. of Commonsense’98, 1998.
• [24] I. Niemela, P. Simons, and T. Soininen. Stable model semantics of weight constraint rules. In Proc. of LPNMR’99, vol. 1730 of LNCS, pp. 317-331. Springer, 1999.
• [25] N. Pelov, M. Denecker, and M. Bruynooghe. Well-founded and stable semantics of logic programs with aggregates. TPLP, 7(3):301-353, 2007.
• [26] R. Pichler, S. Rtimmele, S. Szeider, and S. Woltran. Tractable answer-set programming with weight constraints: Bounded treewidth is not enough. In Proc. ofKR'10. AAAI Press, 2010.
• [27] P. Simons, I. Niemela, and T. Soininen. Extending and implementing the stable model semantics. Artificial Intelligence, 138(1-2):181-234, 2002.
• [28] T. Soininen, I. Niemela, J. Tiihonen, and R. Sulonen. Representing configuration knowledge with weight constraint rules. In Proc. of the AAAI Spring Symposium on Answer Set Programming. AAAI Press, 2001.
• [29] M. Truszczynski. Logic programming for knowledge representation. In V. Dahl and I. Niemela, eds., Proc. of ICLP'07, vol. 4670 of LNCS, pp. 76-88. Springer, 2007.
• [30] H. Turner. Strong equivalence made easy: nested expressions and weight constraints. TPLP, 3(4-5):609-622, 2003.
• [31] D. Van Nieuwenborgh and D. Vermeir. Ordered diagnosis. In Proc. ofLPAR'03, vol. 2850 of LNCS, pp. 244258. Springer, 2003.