Skip Navigation



Journal of Logic and Computation Advance Access published online on November 6, 2009
Journal of Logic and Computation, doi:10.1093/logcom/exp071
This Article
Right arrow Abstract Freely available
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Costantini, S.
Right arrow Articles by Formisano, A.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author, 2009. Published by Oxford University Press. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

Original Papers

Answer Set Programming with Resources

Stefania Costantini

Dipartimento di Informatica, Università di L’Aquila, via Vetoio, I-67010 L’Aquila, Italy.
E-mail: stefcost{at}di.univaq.it

Andrea Formisano

Dipartimento di Matematica e Informatica, Università di Perugia, via Vanvitelli, 1, I-06123 Perugia, Italy.
E-mail: formis{at}dipmat.unipg.it

Received 1 January 2008.

In this article, we propose an extension of Answer Set Programming (ASP) to support declarative reasoning on consumption and production of resources. We call the proposed extension RASP, standing for ‘Resourced ASP’. Resources are modeled by introducing special atoms, called amount-atoms, to which we associate quantities that represent the available amount of a certain resource. The ‘firing’of aRASP rule involving amount-atoms can both consume and produce resources. A RASP rule can be fired several times, according to its definition and to the available quantities of required resources. We define the semantics for RASP programs by extending the usual answer set semantics. Different answer sets correspond to different possible allocations of available resources. We then propose an implementation based on standard ASP-solvers. The implementation consists of a standard translation of each RASP rule into a set of plain ASP-rules and of an inference engine that manages the firing of RASP rules.

Keywords: Answer set programming; non-monotonic logic programming; quantitative reasoning; language extensions



References

  1. Andreoli J-M. Logic programming with focusing proofs in linear logic. Journal of Logic and Computation (1992) 2:297–347.[Abstract/Free Full Text]
  2. Andreoli J-M, Pareschi R. Linear objects: logical processes with built-in inheritance. New Generation Computing (1991) 9:445–473.[CrossRef]
  3. Anger C, Schaub T, Truszczynski M. ASPARAGUS – the dagstuhl initiative. In: ALP Newsletter (2004) 17. Available at http://asparagus.cs.uni-potsdam.de.
  4. Apt KR, Bol RN. Logic programming and negation: a survey. Journal of Logic Programming (1994) 19:9–72.[CrossRef]
  5. Web references for some ASP solvers. ASSAT, http://assat.cs.ust.hk; Ccalc, http://www.cs.utexas.edu/users/tag/ccalc; Clasp, http://www.cs.uni-potsdam.de/clasp; Cmodels, http://www.cs.utexas.edu/users/tag/cmodels; DeReS and aspps, http://www.cs.uky.edu/ai/; DLV, http://www.dbai.tuwien.ac.at/proj/dlv; Smodels, http://www.tcs.hut.fi/Software/smodels.
  6. Baader F, Calvanese D, McGuinness D, Nardi D, Patel-Schneider P. The Description Logic Handbook (2003) Cambridge University Press.
  7. Banbara M. Design and Implementation of Linear Logic Programming Languages (2002) The Graduate School of Science and Technology of Kobe University. PhDThesis.
  8. Banbara M, Tamura N. Compiling resources in a linear logic programming language. In: Proceedings of the Workshop on Parallelism and Implementation Technology for Logic Programming Languages (1998) 32–45. Available at http://www.cs.nmsu.edu/lldap/jicslp98/.
  9. Baral C. Knowledge Representation, Reasoning and Declarative Problem Solving (2003) Cambridge University Press.
  10. Calimeri F, Ianni G. External sources of computation for answer set solvers. Baral C, Greco G, Leone N, Terracina G, eds. (2005) Springer. 105–118. In Procedings of the 8th International Conference on Logic Programming and Nonmonotonic Reasoning, Vol. 3662 of Lecture Notes in Computer Science.
  11. Cervesato I, Pfenning F. A linear logical framework. Clarke E, ed. (1996) IEEE Computer Society Press. 264–275. In Proceedings of the Eleventh Annual Symposium on Logic in Computer Science–LICS’96.
  12. Chintabathina S, Gelfond M, Watson R. Defeasible laws, parallel actions, and reasoning about resources. In: Logical Formalizations of Commonsense Reasoning: Proceedings of CommonSense’07—Amir E, Lifschitz V, Miller R, eds. (2007) AAAI Press. Technical report SS-07-05.
  13. Corona E, Osorio M. TheA-Pol system. In: Answer Set Programming, Advances in Theory and Implementation, Proceedings of the 2nd International ASP’03—De Vos M, Provetti A, eds. (2003) Vol. 78 of CEUR Workshop Proceedings.
  14. Costantini S, Formisano A. Modeling resource production and consumption in answer set programming. In: Proceedings of ASP07 (2007).
  15. Costantini S, Formisano A. Conditional preferences in P-RASP. In: Proceedings of LANMR’08 (2008).
  16. Costantini S, Formisano A. Modeling preferences on resource consumption and production in ASP. In: Proceedings of ASPOCP’08 (2008) Extended version as Report-09/2008 of Dip. di Matematica e Informatica, Univ. di Perugia: available at www.dipmat.unipg.it/~formis/papers/report2008_09.ps.gz.
  17. Costantini S, Formisano A. Modeling preferences and conditional preferences on resource consumption and production in ASP. Journal of Algorithms in Cognition, Informatics and Logic (2009) 64:3–15.
  18. Cox M, Nelson D. Lehninger Principles of Biochemistry (2004) Freeman & Co.
  19. Dal Palù A, Dovier A, Pontelli E, Rossi G. Answer set programming with constraints using lazy grounding. Hill P, Warren D, eds. (2009) Springer. In Logic Programming, 25st International Conference, ICLP 2009, Proceedings, Vol. 5649 of Lecture Notes in Computer Science.
  20. Dantsin E, Eiter T, Gottlob G, Voronkov A. Complexity and expressive power of logic programming. ACM Computing Surveys (2001) 33:374–425.[CrossRef][Web of Science]
  21. Dovier A, Formisano A, Pontelli E. An empirical study of constraint logic programming and answer set programming solutions of combinatorial problems. Journal of Experimental and Theoretical Artificial Intelligence (2009) 21:79–121.[CrossRef]
  22. Eiter T, Ianni G, Schindlauer R, Tompits H. A uniform integration of higher-order reasoning and external evaluations in answer-set programming. Kaelbling LP, Saffiotti A, eds. (2005) Professional Book Center. 90–96. In Proceedings of the 19th International Joint Conference on Artificial Intelligence.
  23. Faber W, Pfeifer G, Leone N, Dell’Armi T, Ielpa G. Design and implementation of aggregate functions in the DLV system. Theory and Practice of Logic Programming (2008) 8:545–580.[CrossRef][Web of Science]
  24. Formisano A, Petturiti D. Extending and implementing RASP. In: Proceedings of CILC’09—Gavanelli M, Riguzzi F, eds. (2009).
  25. Gebser M, Schaub T, Thiele S. GrinGo: A new grounder for answer set programming. Baral C, Brewka G, Schlipf JS, eds. (2007) Springer. 266–271. In Proceedings of the 9th International Conference on Logic Programming and Nonmonotonic Reasoning, Vol. 4483 of Lecture Notes in Computer Science.
  26. Gelfond M. Answer sets. In: Handbook of Knowledge Representation (2007) Elsevier.
  27. Gelfond M, Lifschitz V. The stable model semantics for logic programming. Kowalski R, Bowen K, eds. (1988) The MIT Press. 1070–1080. In Proceedings of the 5th International Conference and Symposium on Logic Programming.
  28. Gelfond M, Lifschitz V. Action languages. Electronic Transactions on AI (1998) 3:193–210.
  29. Girard J-Y. Linear logic. Theoretical Computer Science (1987) 50:1–102.[CrossRef][Web of Science]
  30. Harland J, Pym D. A uniform proof-theoretic investigation of linear logic programming. Journal of Logic and Computation (1994) 4:175–207.[Abstract/Free Full Text]
  31. Harland J, Pym D, Winikoff M. Programming in lygon: an overview. In: Algebraic Methodology and Software Technology—Wirsing M, Nivat M, eds. (1996) Springer. 391–405. Vol. 1101 of Lecture Notes in Computer Science.
  32. Hodas JS. Logic Programming in Intuitionistic Linear Logic: Theory, Design and Implementation (1994) University of Pennsylvania, Department of Computer and Information Science. PhD Thesis.
  33. Hodas JS, Miller D. Logic programming in a fragment of intuitionistic linear logic. Information and Computation (1994) 110:327–365.[CrossRef][Web of Science]
  34. Hodas JS, Polakow J. Forum as a logic programming language: preliminary results and observations. In: Proceedings of the Linear Logic’96 Meeting—Okada M, ed. (1996) 3. Elsevier Electronic Notes in Theoretical Computer Science.
  35. Jacquet J-M, Monteiro L. Towards resource handling in logic programming: the PPL framework and its semantics. Computer Languages (1996) 22:51–77.[CrossRef][Web of Science]
  36. Kemp DB, Stuckey PJ. Semantics of logic programs with aggregates. (1991) The MIT Press. 387–401. In Proceedings of the 1991 International Logic Programming Symposium.
  37. Kobayashi N, Yonezawa A. Acl - a concurrent linear logic programming paradigm. Miller D, ed. (1993) MIT Press. 279–294. In Proceedings of the 1993 International Logic Programming Symposium.
  38. Kobayashi N, Yonezawa A. Asynchronous communication model based on linear logic. Formal Aspects of Computing (1994) 3:279–294.
  39. Lefèvre C, Nicolas P. A first order forward chaining approach for answer set computing. (2009) Springer. In Proceedings of the 10th International Conference on Logic Programming and Nonmonotonic Reasoning LPNMR’09, Lecture Notes in Computer Science.
  40. Leone N. Logic programming and nonmonotonic reasoning: from theory to systems and applications. Baral C, Brewka G, Schlipf JS, eds. (2007) Springer. 1. In Logic Programming and Nonmonotonic Reasoning, 9th International Conference, LPNMR 2007.
  41. Lifschitz V. Answer set planning. (1999) Springer. 23–37. In Proceedings of the 16th International Conference on Logic Programming.
  42. Lifschitz V, Turner H. Splitting a logic program. (1994) 23–37. In International Conference on Logic Programming, (ICLP).
  43. Lloyd JW. Foundations of Logic Programming (1987) Springer.
  44. Marek VW, Truszczynski M. Logic programming with costs. Unpublished Note.
  45. Marek VW, Truszczynski M. Autoepistemic logic. Journal of the ACM (1991) 38:587–618.[CrossRef]
  46. Marek VW, Truszczynski M. Computing intersection of autoepistemic expansions. In: Proceedings of the First International Workshop on Logic Programming and Non Monotonic Reasoning (1991) The MIT Press. 35–70.
  47. Marek VW, Truszczynski M. Stable Logic Programming - an Alternative Logic Programming Paradigm (1999) Springer. 375–398.
  48. Miller D. Linear logic programming references. (1995) Available at ftp://ftp.cis.upenn.edu/pub/papers/miller/ComputNet95/llsurvey.html.
  49. Miller D. A multiple-conclusion specification logic. Theoretical Computer Science (1996) 165:201–232.[CrossRef][Web of Science]
  50. Miller D, Nadathur G, Pfenning F, Scedrov A. Uniform proofs as a foundation for logic programming. Annals of Pure and Applied Logic (1991) 51:125–157.[CrossRef][Web of Science]
  51. Niemelä I, Simons P, Soininen T. Stable model semantics of weight constraint rules. (1999) Springer. 317–331. In Proceedings of the 5th International Conference on Logic Programming and Nonmonotonic Reasoning LPNMR’99, Vol. 1730 in Lecture Notes in Artificial Intelligence.
  52. Niemelä I, Simons P, Syrjänen T. Smodels: a system for answer set programming. In: Proceedings of the 8th Workshop on Non-Monotonic Reasoning (2000).
  53. Nieuwenborgh DV, Heymans S, Vermeir D. Weighted answer sets and applications in intelligence analysis. In: Proceedings LPAR 2004 (2005) Springer. 169–183. Vol. 3452 in Lecture Notes in Artificial Intelligence.
  54. Ryu YU. Alogic-based modeling of resource consumption and production. Decision Support Systems (1998) 22:243–257.[CrossRef][Web of Science]
  55. Simons P, Niemelä I, Soininen T. Extending and implementing the stable model semantics. Artificial Intelligence (2002) 138:181–234.[CrossRef][Web of Science]
  56. Soininen T, Niemelä I. Developing a declarative rule language for applications in product configuration. In: Proceedings of the First International Workshop on Practical Aspects of Declarative Languages (1999) Springer. 305–319. Vol. 1551 in Lecture Notes in Computer Science.
  57. Soininen T, Niemelä I, Tiihonen J, Sulonen R. Representing configuration knowledge with weight constraint rules. (2001) AAAI Press. In Proceedings of the AAAI Spring 2001 Symposium on Answer Set Programming (ASP’01): Towards Efficient and Scalable Knowledge. Technical Report SS-01-01.
  58. Son TC, Pontelli E. A constructive semantic characterization of aggregates in answer set programming. Theory and Practice of Logic Programming (2007) 7.
  59. Tamura N, Kaneda Y. Extension of WAM for a linear logic programming language. In: Second Fuji International Workshop on Functional and Logic Programming—Ida T, Ohori A, Takeichi M, eds. (1996) World Scientific. 33–50.
  60. Truszczynski M. Logic programming for knowledge representation. Dahl V, Niemelä I, eds. (2007) 76–88. In Logic Programming, 23rd International Conference, ICLP 2007.

Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?



This Article
Right arrow Abstract Freely available
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Costantini, S.
Right arrow Articles by Formisano, A.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?