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: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1993-264
BibTeX
@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},
}