No CrossRef data available.
Article contents
On finitely recursive programs1
Published online by Cambridge University Press: 11 March 2009
Abstract
Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.
Disjunctive finitary programs are a class of logic programs admitting function symbols and hence infinite domains. They have very good computational properties; for example, ground queries are decidable, while in the general case the stable model semantics are Π11-hard. In this paper we prove that a larger class of programs, called finitely recursive programs, preserve most of the good properties of finitary programs under the stable model semantics, which are as follows: (i) finitely recursive programs enjoy a compactness property; (ii) inconsistency checking and skeptical reasoning are semidecidable; (iii) skeptical resolution is complete for normal finitely recursive programs. Moreover, we show how to check inconsistency and answer skeptical queries using finite subsets of the ground program instantiation. We achieve this by extending the splitting sequence theorem by Lifschitz and Turner: we prove that if the input program P is finitely recursive, then the partial stable models determined by any smooth splitting ω-sequence converge to a stable model of P.
Keywords
Information
- Type
- Regular Papers
- Information
- Copyright
- Copyright © Cambridge University Press 2009
References
Baral, C. 2003. Knowledge Representation, Reasoning and Declarative Problem Solving. Cambridge University Press, Cambridge.CrossRefGoogle Scholar
Baselice, S., Bonatti, P. A. and Criscuolo, G. 2007. On finitely recursive programs. In ICLP, Dahl, V. and Niemelä, I., Eds. Lecture Notes in Computer Science, vol. 4670. Springer, 89–103.Google Scholar
Bonatti, P. A. 1993. Shift-Based Semantics: General Results and Applications. Tech. Rep. CD-TR 93/59, Computer Science Department, Institute of Information Systems, Technical University of Vienna, Vienna.Google Scholar
Bonatti, P. 2001a. Prototypes for reasoning with infinite stable models and function symbols. In Logic Programming and Nonmonotonic Reasoning, 6th International Conference, LPNMR 2001, Eiter, T., Faber, W., and Truszczynski, M., Eds. Lecture Notes in Computer Science, vol. 2173. Springer, Vienna, Austria, 416–419.Google Scholar
Bonatti, P. A. 2001b. Resolution for skeptical stable model semantics. Journal of Automatic Reasoning 27, 4, 391–421.CrossRefGoogle Scholar
Bonatti, P. A. 2002. Reasoning with infinite stable models II: Disjunctive programs. In ICLP, Stuckey, P. J., Ed. Lecture Notes in Computer Science, vol. 2401. Springer, 333–346.Google Scholar
Bonatti, P. A. 2004. Reasoning with infinite stable models. Artificial Intelligence 156, 1, 75–111.CrossRefGoogle Scholar
Calimeri, F., Cozza, S., Ianni, G. and Leone, N. 2008. Computable functions in ASP: Theory and implementation. In ICLP, de la Banda, M. G. and Pontelli, E., Eds. Lecture Notes in Computer Science, vol. 5366. Springer, 407–424.Google Scholar
Eiter, T., Leone, N., Mateis, C., Pfeifer, G. and Scarcello, F. 1997. A deductive system for non-monotonic reasoning. In Logic Programming and Nonmonotonic Reasoning, 4th International Conference, LPNMR'97, Proceedings, Dix, J., Furbach, U., and Nerode, A., Eds. Lecture Notes in Computer Science, vol. 1265. Springer, Dagstuhl, Germany, 364–375.Google Scholar
Fages, F. 1994. Consistency of Clark's completion and existence of stable models. Methods of Logic in Computer Science 1, 51–60.Google Scholar
Gelfond, M. and Lifschitz, V. 1988. The stable model semantics for logic programming. In Proc. of the 5th ICLP. MIT Press, 1070–1080.Google Scholar
Gelfond, M. and Lifschitz, V. 1991. Classical negation in logic programs and disjunctive databases. New Generation Computing 9, 3–4, 365–386.CrossRefGoogle Scholar
Lifschitz, V. and Turner, H. 1994. Splitting a logic program. In International Conference on Logic Programming, Van Entenryck, P., Ed. S. Margherita Ligure, MIT Press, 23–37.Google Scholar
Marek, V. and Remmel, J. 2001. On the expressibility of stable logic programming. In Logic Programming and Nonmonotonic Reasoning, 6th International Conference, LPNMR 2001, Eiter, T., Faber, W., and Truszczynski, M., Eds. Lecture Notes in Computer Science, vol. 2173. Springer, Vienna, Austria, 107–120.Google Scholar
Marek, V. W. and Truszczynski, M. 1998. Stable models and an alternative logic programming paradigm. Computing Research Repository, CoRR cs.LO/9809032. (http://arxiv.org/corr)CrossRefGoogle Scholar
Niemelä, I. 1999. Logic programs with stable model semantics as a constraint programming paradigm. Annals of Mathematics and Artificial Intelligence 25, 3–4, 241–273.CrossRefGoogle Scholar
Niemelä, I. and Simons, P. 1997. Smodels–-an implementation of the stable model and well-founded semantics for normal LP. In Logic Programming and Nonmonotonic Reasoning, 4th International Conference, LPNMR'97, Proceedings, Dix, J., Furbach, U., and Nerode, A., Eds. Lecture Notes in Computer Science, vol. 1265. Springer, Dagstuhl, Germany, 421–430.Google Scholar
Simkus, M. and Eiter, T. 2007. FDNC: Decidable non-monotonic disjunctive logic programs with function symbols. In 14th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning, LPAR 2007, Dershowitz, N. and Voronkov, A., Eds. Lecture Notes in Computer Science, vol. 4790. Springer, Yerevan, Armenia, 514–530.Google Scholar
Turner, H. 1994. Signed logic programs. In SLP, Bruynooghe, M., Ed. MIT Press, Itaha, New York, 61–75.Google Scholar
Turner, H. 1996. Splitting a default theory. In Proceedings of the Thirteenth National Conference on Artificial Intelligence, Shrobe, H. and Senator, T., Eds. AAAI Press, Menlo Park, CA, 645–651.Google Scholar
You have
Access
- 15
- Cited by