On finitely recursive programs
- 11 March 2009
- journal article
- research article
- Published by Cambridge University Press (CUP) in Theory and Practice of Logic Programming
- Vol. 9 (02), 213-238
- https://doi.org/10.1017/s147106840900372x
Abstract
Disjunctivefinitary programsare 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, calledfinitely 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 programPis finitely recursive, then the partial stable models determined by any smooth splitting ω-sequence converge to a stable model ofP.Keywords
This publication has 7 references indexed in Scilit:
- $\mathbb{FDNC}$ : Decidable Non-monotonic Disjunctive Logic Programs with Function SymbolsLecture Notes in Computer Science, 2007
- Reasoning with infinite stable modelsArtificial Intelligence, 2004
- Knowledge Representation, Reasoning and Declarative Problem SolvingPublished by Cambridge University Press (CUP) ,2003
- Resolution for Skeptical Stable Model SemanticsJournal of Automated Reasoning, 2001
- Logic programs with stable model semantics as a constraint programming paradigmAnnals of Mathematics and Artificial Intelligence, 1999
- Classical negation in logic programs and disjunctive databasesNew Generation Computing, 1991
- Foundations of Logic ProgrammingPublished by Springer Science and Business Media LLC ,1984