Transitive Closure, Answer Sets and Predicate Completion
Esra Erdem, Vladimir Lifschitz · 2001
We prove that the usual logic programming denition of transitive closure is correct under the answer set semantics, and investigate under what conditions it is correct under the completion semantics. That denition is allowed here to be combined with an arbitrary set of rules that may contain negation as failure, not merely with a set of facts. This work is motivated by applications to answer set programming. 1 Introduction In logic programming, the transitive closure tc of a binary predicate p is usually dened by the rules tc(x; y) p(x; y); tc(x; y) p(x; v); tc(v; y): If we combine this denition Def with any set of facts (that is, ground atoms) dening p, and consider the minimal model of the resulting program, the extent of tc in this model will be the transitive closure of the extent of p. In this sense, Def is a correct characterization of the concept of transitive closure. We know, on the other hand, that the completion of [Def in the sense of Clark [1978] may ha...