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.
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
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.
Full Paper (gzipped postscript 215K)