FDNC
- 22 January 2010
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computational Logic
- Vol. 11 (2), 1-50
- https://doi.org/10.1145/1656242.1656249
Abstract
We present the class FDNC of logic programs that allows for function symbols (F), disjunction (D), nonmonotonic negation under the answer set semantics (N), and constraints (C), while still retaining the decidability of the standard reasoning tasks. Thanks to these features, FDNC programs are a powerful formalism for rule-based modeling of applications with potentially infinite processes and objects, and which allows also for common-sense reasoning in this context. This is evidenced, for instance, by tasks in reasoning about actions and planning: brave and open queries over FDNC programs capture the well-known problems of plan existence and secure (conformant) plan existence, respectively, in transition-based actions domains. As for reasoning from FDNC programs, we show that consistency checking and brave/cautious reasoning tasks are ExpTime-complete in general, but have lower complexity under syntactic restrictions that give rise to a family of program classes. Furthermore, we also determine the complexity of open queries (i.e., with answer variables), for which deciding non-empty answers is shown to be ExpSpace -complete under cautious entailment. Furthermore, we present algorithms for all reasoning tasks that are worst-case optimal. The majority of them resorts to a finite representation of the stable models of an FDNC program that employs maximal founded sets of knots, which are labeled trees of depth at most 1 from which each stable model can be reconstructed. Due to this property, reasoning over FDNC programs can in many cases be reduced to reasoning from knots. Once the knot-representation for a program is derived (which can be done off-line), several reasoning tasks are not more expensive than in the function-free case, and some are even feasible in polynomial time. This knowledge compilation technique paves the way to potentially more efficient online reasoning methods not only for FDNC, but also for other formalisms.Keywords
Funding Information
- Austrian Science Fund (P17212P21840)
- Sixth Framework Programme (IST-2003-506779)
This publication has 25 references indexed in Scilit:
- Domain-dependent knowledge in answer set planningACM Transactions on Computational Logic, 2006
- On the expressibility of stable logic programmingTheory and Practice of Logic Programming, 2003
- A logic programming approach to knowledge-state planning, II: TheArtificial Intelligence, 2003
- Answer set programming and plan generationArtificial Intelligence, 2002
- Complexity and expressive power of logic programmingACM Computing Surveys, 2001
- Expressiveness of stable model semantics for disjunctive logic programs with functionsThe Journal of Logic Programming, 1997
- Depth-bounded bottom-up evaluation of logic programsThe Journal of Logic Programming, 1995
- Finite representation of infinite query answersACM Transactions on Database Systems, 1993
- Nonmonotonic logic and temporal projectionArtificial Intelligence, 1987
- Unification as a complexity measure for logic programmingThe Journal of Logic Programming, 1987