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):|
|Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView|