Proceedings

Bidirectional Answer Set Programs with Function Symbols

Download BibTeX Cite

Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence. Pages 765-770.

© 2009 International Joint Conferences on Artificial Intelligence

Abstract

Current Answer Set Programming (ASP) solvers largely build on Datalog, which, unlike general logic programming, lacks function symbols. This limitation makes ASP decidable, but greatly complicates the modeling of indefinite time, recursive data structures (e.g., lists), and infinite processes and objects in general. Recent research thus aims at finding decidable fragments of ASP with function symbols and studying their complexity. We identify bidirectional ASP programs as an expressive, but yet decidable, language that is useful, e.g., for reasoning about actions involving both the future and the past. We tightly characterize the computational complexity of bidirectional programs and some of their subclasses, addressing the main reasoning tasks. Our results also show that the recently introduced FDNC programs can be extended by inverse rules while retaining decidability, but computational costs are unavoidably higher.Thomas Eiter, Mantas Simkus

  1. [Baral, 2002] C. Baral. Knowledge Representation, Reasoning and Declarative Problem Solving. CUP, 2002.
  2. [Baselice et al., 2007] S. Baselice, P. A. Bonatti, and G. Criscuolo. On finitely recursive programs. In ICLP-07, LNCS 4670, pp. 89-103. Springer, 2007.
  3. [Bonatti, 2004] P. A. Bonatti. Reasoning with infinite stable mod- els. Artif. Intell., 156(1):75-111, 2004. IJCAI
  4. [Calimeri et al., 2008] F. Calimeri, S. Cozza, G. Ianni, and N. Leone. Computable functions in ASP: Theory and implemen- tation. In ICLP-08, LNCS 5366, pp. 407-424. Springer, 2008.
  5. [Chomicki and Imielinski, 1993] J. Chomicki and T. Imielinski. Fi- nite representation of infinite query answers. ACM Trans. Database Syst., 18(2):181-223, 1993.
  6. [Gelfond and Lifschitz, 1991] M. Gelfond and V. Lifschitz. Clas- sical negation in logic programs and disjunctive databases. New Gen. Comput., 9(3/4):365-386, 1991.
  7. [Heymans, 2006] Stijn Heymans. Decidable Open Answer Set Pro- gramming. Ph.D. Dissertation. Vrije Universiteit Brussel, 2006.
  8. [Marek et al., 1994] W. Marek, A. Nerode, and J. Remmel. The Stable Models of a Predicate Logic Program. Journal of Logic Programming, 21(3):129-153, 1994.
  9. [Minker, 1988] J. Minker (ed). Foundations of Deductive Data- bases & Logic Programming. Morgan Kaufm., 1988.
  10. [Simkus and Eiter, 2007] M. Simkus and T. Eiter. FDNC: De- cidable non-monotonic disjunctive logic programs with function symbols. In LPAR-07, LNCS 4790, pp. 514-530. Springer, 2007.
  11. [Syrjänen, 2001] T. Syrjänen. Omega-restricted logic programs. In LPNMR-01, LNCS 2173, pp. 267-279. Springer, 2001.
  12. [Thomas, 1990] W. Thomas. Automata on infinite objects. In Handbook of Theor. Comp. Sci. (B), pp. 133-192. Elsevier, 1990.
  13. [Vardi, 1998] Moshe Y. Vardi. Reasoning about the past with two- way automata. In Proc. ICALP-98, LNCS 1443, pp. 628-641.
  14. [Woltran, 2005] S. Woltran. Answer Set Programming: Model ap- plications and proofs-of-Concept. Available at http://www. kr.tuwien.ac.at/projects/WASP/report.html. Link

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards