Studies on Disjunctive Logic Programming

Chiaki Sakama

Dissertation, Kyoto University, 1994.


Recent studies have enriched the expressive power of logic programming as a knowledge representation tool and the growing importance of logic programming in artificial intelligence is well recognized these days. Disjunctive logic programming is one of such extensions of logic programming which provides us with the ability of reasoning with indefinite information. Due to their expressiveness, disjunctive logic programming has been given an increasing attention over the past few years.

In this dissertation, we study theoretical frameworks for disjunctive logic programming. Our particular interest is in the semantic issues of disjunctive logic programs and their correspondences to commonsense reasoning in artificial intelligence. As a semantics of disjunctive logic programs, we propose a new declarative semantics called the possible model semantics. The possible model semantics is an alternative theoretical framework for disjunctive logic programs, which provides a flexible inference mechanism for representing knowledge and also has a computational advantage over the classical minimal model semantics. To relate disjunctive logic programs to commonsense reasoning in artificial intelligence, we propose transformations from disjunctive logic programs to various forms of nonmonotonic reasoning such as default logic, circumscription, and autoepistemic logic. Moreover, we discuss connections between disjunctive logic programs and abductive logic programs, and reveal close relationships between each framework. Another important issue for commonsense reasoning is the treatment of inconsistent knowledge. Since classical logic programming is not useful in inconsistent programs, we introduce paraconsistent semantics for disjunctive logic programs which provide uniform frameworks for handling both indefinite and inconsistent information in a program. We finally discuss program optimization issues in disjunctive logic programs. A technique of partial deduction in logic programming is extended to disjunctive logic programs and its correctness is presented.

Thesis (pdf 708K) (Printed copies are available on request basis.)