Incremental answer sets and their computation
Martin Gebser, Mona Gharib, Torsten H. Schaub · 2007
In answer set programming, the existence of an answer set for a logic program is not guaranteed. In order to remedy this problem, we utilize the alternative concept of ι-answer sets, which are characterized by their applied rules. The ι-answer sets of a logic program amount to the justified extensions of the default theory corresponding to the program. On the one hand, every logic program has at least one ι-answer set, which can be constructed incrementally based on applicable rules. On the other hand, a ι-answer set may lack characteristic properties of standard answer sets, such as being a model of the given program. We show how integrity constraints can be used to re-establish such properties, even up to correspondence with standard answer sets. Furthermore, we introduce a translation from logic programs to propositional formulas that modifies Clark’s completion to preserve the ι-answer sets of a given program. Based on our notion of program completion, we present a DPLL-like algorithm for computing the ι-answer sets of a logic program that satisfy a given set of integrity constraints.