A general theory of confluent rewriting systems for logic programming and its applications Original Research Article

Recently, Brass and Dix showed (J. Automat. Reason. 20(1) (1998) 143–165) that the well founded semantics WFS can be defined as a confluent calculus of transformation rules. This led not only to a simple extension to disjunctive programs (J. Logic Programming 38(3) (1999) 167–213), but also to a new computation of the well-founded semantics which is 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 Confluent LP-systemsView the MathML source. Such a system View the MathML source is a rewriting system on the set of all logic programs over a fixed signature View the MathML source and it induces in a natural way a canonical semantics. Moreover, we show four important applications of this theory: (1) most of the well-known semantics are induced by confluent LP-systems, (2) there are many more transformation rules that lead to confluent LP-systems, (3) semantics induced by such systems can be used to model aggregation, (4) the new systems can be used to construct interesting counterexamples to some conjectures about the space of well-behaved semantics.