Extending and Implementing RASP

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

Abstrakty

EN

In previous work we have proposed an extension to ASP (Answer Set Programming), called RASP, standing for ASP with Resources. RASP supports declarative reasoning on production and consumption of (amounts of) resources. The approach combines answer set semantics with quantitative reasoning and relies on an algebraic structure to support computations and comparisons of amounts. The RASP framework provides some form of preference reasoning on resources usage. In this paper, we go further in this direction by introducing expressive constructs for supporting complex preferences specification on aggregate resources. We present a refinement of the semantics of RASP so as to take into account the new constructs. For all the extensions, we provide an encoding into plain ASP.We prove that the complexity of establishing the existence of an answer set, in such an enriched framework, remains NP-complete as in ASP. Finally, we report on raspberry, a prototypical implementation of RASP. This tool consists of a compiler that, given a ground RASP program, produces a pure ASP encoding suitable to be processed by commonly available ASP-solvers.

Słowa kluczowe

EN

answer set programming; quantitative reasoning; preferences; language extensions

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 105, nr 1/2
• Strony: 1--33
• Opis fizyczny: Bibliogr. 26 poz., tab.

Twórcy

autor

Costantini S.

autor

Formisano A.

autor

Petturiti D.

• Dipartimento di Informatica, Universita di L'Aquila, Piazza Vincenzo Rivera, 1 - 67100, Italy,

Bibliografia

• [1] C. Baral. Knowledge representation, reasoning and declarative problem solving. Cambridge University Press, 2003.
• [2] S. M. Brasil, Jr. Rules and principles in legal reasoning: A study of vagueness and collisions in artificial intelligence and law. Information & Communications Technology Law, 10(1), 2001.
• [3] G. Brewka. Complex preferences for answer set optimization. In D. Dubois, C. A.Welty, and M.-A.Williams, eds., Proceedings of KR'04, pages 213-223. AAAI Press, 2004.
• [4] G. Brewka, I. Niemelä, and T. Syrjänen. Logic programs with ordered disjunction. Computational Intelligence, 20(2):335-357, 2004.
• [5] G. Brewka, I. Niemelä, and M. Truszczyński. Preferences and nonmonotonic reasoning. AI Magazine, 29(4), 2010.
• [6] R. Caspi et al. The MetaCyc database of metabolic pathways and enzymes and the BioCyc collection of pathway/genome databases. Nucleic Acids Research, 38, 2010.
• [7] S. Costantini and A. Formisano. Modeling preferences and conditional preferences on resource consumption and production in ASP. Journal of of Algorithms in Cognition, Informatics and Logic, 64(1), 2009.
• [8] S. Costantini and A. Formisano. Answer set programming with resources. Journal of Logic and Computation, 20(2):533-571, 2010.
• [9] M. Cox and D. Nelson. Lehninger Principles of Biochemistry. Freeman&Co., 2004.
• [10] A. Dal Pal`u, A. Dovier, E. Pontelli, and G. Rossi. GASP: Answer set programming with lazy grounding. Fundamenta Informaticae, 96, 2009.
• [11] W. Faber, G. Pfeifer, N. Leone, T. Dell'Armi, and G. Ielpa. Design and implementation of aggregate functions in the DLV system. Theory and Practice of Logic Programming, 8(5-6):545-580, 2008.
• [12] M. Gebser, T. Schaub, and S. Thiele. GrinGo: A new grounder for answer set programming. In C. Baral, G. Brewka, and J. Schlipf, eds., Proc. of LPNMR'07, volume 4483 of LNCS, pages 266-271. Springer, 2007.
• [13] M. Gelfond. Answer sets. In Handbook of Knowledge Representation, chapter 7. Elsevier, 2007.
• [14] M. Gelfond and V. Lifschitz. The stable model semantics for logic programming. In R. Kowalski and K. Bowen, eds., Proceedings of ICLP/SLP'88, pages 1070-1080. The MIT Press, 1988.
• [15] P. Kärger, N. Lopes, A. Polleres, and D. Olmedilla. Towards logic programs with ordered and unordered, disjunction. In Proceedings of ASPOCP'08 Workshop of ICLP'08, 2008.
• [16] D. B. Kemp and P. J. Stuckey. Semantics of logic programs with aggregates. In V. A. Saraswat and K. Ueda, eds., Proceedings of ILPS'91, pages 387-401. The MIT Press, 1991.
• [17] N. Leone. Logic programming and nonmonotonic reasoning: From theory to systems and applications. In C. Baral, G. Brewka, and J. Schlipf, eds., Proc. of LPNMR'07, volume 4483 of LNCS, page 1. Springer, 2007.
• [18] V. Lifschitz. Answer set planning. In D. De Schreye, ed., Proceedings of ICLP'99, pages 23-37. The MIT Press, 1999.
• [19] V. Lifschitz and H. Turner. Splitting a logic program. In Proceedings of ICLP'94, pages 23-37. The MIT Press, 1994.
• [20] N. M. Luscombe, D. Greenbaum, and M. Gerstein. What is bioinformatics? A proposed definition and overview of the field. Methods of Information in Medicine, 40(4):346-358, 2001.
• [21] C. K. Mathews, K. E. van Holde, and K. G. Ahern. Biochemistry. Prentice Hall, 1999.
• [22] H. Prakken and G. Sartor. Argument-based logic programming with defeasible priorities. Journal of Applied Non-classical Logics, 7, 1997. Special issue on "Handling inconsistency in knowledge systems".
• [23] T. Son and E. Pontelli. A constructive semantic characterization of aggregates in answer set programming. Theory and Practice of Logic Programming, 7(3), 2007.
• [24] M. Truszczyński. Logic programming for knowledge representation. In V. Dahl and I. Niemelä, eds., Proceedings of ICLP'07, volume 4670 of LNCS, pages 76-88. Springer, 2007.
• [25] Web reference for Raspberry: http://www.dmi.unipg.it/~formis/raspberry/.
• [26] Web references for some ASP solvers. Clasp: http://http://potassco.sourceforge.net; Cmodels: http://www.cs.utexas.edu/users/tag/cmodels; DLV: http://www.dbai.tuwien.ac.at/ proj/dlv; Smodels: http://www.tcs.hut.fi/Software/smodels.