On the Equivalence between Disjunctive and Abductive Logic Programs

Chiaki Sakama and Katsumi Inoue

Proceedings of the 11th International Conference on Logic Programming (ICLP'94), pp. 489-503, MIT Press, 1994.

Abstract

This paper presents the equivalence relationship between disjunctive and abductive logic programs. We show that the generalized stable model semantics of abductive logic programs can be translated into the possible model semantics of disjunctive programs, and vice versa. It is also proved that abductive disjunctive programs can be expressed by abductive logic programs under the possible model semantics. Furthermore, when considering the disjunctive stable model semantics instead of the possible model semantics, it is unlikely that disjunctive programs can be efficiently expressed in terms of the generalized stable model semantics. The results of this paper reveal that disjunctive programs and abductive logic programs are just different ways of looking at the same problem if we choose the appropriate semantics.

Full Paper (pdf 261K)