Abductive Logic Programming and Disjunctive Logic Programming: Their Relationship and Transferability

Chiaki Sakama and Katsumi Inoue

Journal of Logic Programming 44(1-3):75-100, Elsevier, 2000.

Abstract

Abductive logic programming (ALP) and disjunctive logic programming (DLP) are two different extensions of logic programming. This paper investigates the relationship between ALP and DLP from the program transformation viewpoint. It is shown that the belief set semantics of an abductive program is expressed by the answer set semantics and the possible model semantics of a disjunctive program. In converse, the possible model semantics of a disjunctive program is equivalently expressed by the belief set semantics of an abductive program, while such a transformation is generally impossible for the answer set semantics. Moreover, it is shown that abductive disjunctive programs are always reducible to disjunctive programs both under the answer set semantics and the possible model semantics. These transformations are verified from the complexity viewpoint. The results of this paper %reveal the close relationship between ALP and DLP, turn out that ALP and DLP are just different ways of looking at the same problem if we choose an appropriate semantics.