GRAPH-THEORETICAL STRUCTURES IN LOGIC PROGRAMS AND DEFAULT THEORIES

In this paper we present a graph representation of logic programs and default theories. We show that many of the semantics proposed for logi c programs with negation can be expressed in terms of notions emerging from graph theory, establishing in this way a link between the fields . Namely the stable models, the partial stable models, and the well-fo unded semantics correspond respectively to the kernels, semikernels an d the initial acyclic part of an associated graph. This link allows us to consider both theoretical (existence, uniqueness) and computationa l problems (tractability, algorithms, approximations) from a more abst ract and rather combinatorial point of view. It also provides a clear and intuitive understanding about how conflicts between rules are reso lved within the different semantics. Furthermore, we extend the basic framework developed for logic programs to the case of Default Logic by introducing the notions of partial, deterministic and well-founded ex tensions for default theories. These semantics capture different ways of reasoning with a default theory.