Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


Graph theoretical structures in logic programs and default theories

Dimopoulos, Yannis and Torres, Alberto

MPI-I-93-264. November 1993, 28 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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.
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-93-264.pdfMPI-I-93-264.pdf13490 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document:
Hide details for BibTeXBibTeX
  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},