MPI-INF Logo
MPI-INF/SWS Research Reports 1991-2017

2. Number - only D2

MPI-I-93-264

Graph theoretical structures in logic programs and default theories

Dimopoulos, Yannis and Torres, Alberto

November 1993, 28 pages.

.
Status: available - back from printing

In this paper we present a graph representation of logic programs and default theories. We show that many of the semantics proposed for logic programs 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-founded semantics correspond respectively to the kernels, semikernels and the initial acyclic part of the associated graph. This link allows us to consider both theoretical problems (existence, uniqueness) and computational problems (tractability, algorithms, approximations) from a more abstract and rather combinatorial point of view. It also provides a clear and intuitive understanding about how conflicts between rules are resolved 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 extensions for default theories. These semantics capture different ways of reasoning with a default theory.

URL to this document: http://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1993-264

Hide details for BibTeXBibTeX
@TECHREPORT{Dimopoulos-93-mpii264,
  AUTHOR = {Dimopoulos, Yannis and Torres, Alberto},
  TITLE = {Graph theoretical structures in logic programs and default theories},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-93-264},
  MONTH = {November},
  YEAR = {1993},
  ISSN = {0946-011X},
}