A General Theory of Confluent rewriting Systems for Logic Programming
and its Applications
A General Theory of Confluent rewriting Systems for Logic Programming
and its Applications
No Thumbnail Available
Files
Publication or External Link
Date
1999-09-11
Authors
Dix, Juergen
Osorio, Mauricio
Advisor
Citation
DRUM DOI
Abstract
Recently, Brass and Dix showed (\emph{Journal of Automated Reasoning}
\textbf{20(1)}, 1998) that the wellfounded semantics WFS can be defined as
a confluent calculus of transformation rules. This lead not only to a
simple extension to disjunctive programs (\emph{Journal of Logic
Programming} \textbf{38(3)}, 1999), but also to a new computation of the
wellfounded semantics which is \emph{linear} for a broad class of
programs. We take this approach as a starting point and generalize it
considerably by developing a general theory of \emph{Confluent LP-Systems}
$\cfs$. Such a system $\cfs$ is a rewriting system on the set of all logic
programs over a fixed signature $\Lang$ and it induces in a natural way a
canonical semantics. Moreover, we show four important applications of
this theory: \emph{(1) most of the well-known semantics are induced by
confluent LP-systems}, \emph{(2) there are many more transformation rules
that lead to confluent LP-systems}, \emph{(3) semantics induced by such
systems can be used to model aggregation}, \emph{(4) the new systems can
be used to construct interesting counterexamples to some conjectures about
the space of well-behaved semantics}.
Also cross-referenced as UMIACS-TR-99-46