An Alternative Approach to the Semantics of Disjunctive Logic Programs and Deductive Databases

Chiaki Sakama and Katsumi Inoue

Journal of Automated Reasoning 13:145-172, Kluwer Academic Publishers, 1994.


In this paper, we study a new semantics of logic programming and deductive databases. The possible model semantics is introduced as a declarative semantics of disjunctive logic programs. The possible model semantics is an alternative theoretical framework to the classical minimal model semantics and provides a flexible inference mechanism for inferring negation in disjunctive logic programs. We also present a proof procedure for the possible model semantics and show that the possible model semantics has an advantage from the computational complexity point of view.

Full Paper (gzipped postscript 117K)