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

Recently, Brass and Dir showed (J. Automat. Reason. 20(1) (1998) 143-165) t hat the well founded semantics WFS can be defined as a confluent calculus o f transformation rules. This led not only to a simple extension to disjunct ive 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 clas s of programs. We take this approach as a starting point and generalize it considerably by developing a general theory of Confluent LP-systems CL. Suc h a system CL is a rewriting system on the set of all logic programs over a fixed signature L and it induces in a natural way a canonical semantics. M oreover, we show four important applications of this theory: (1) most of th e well-known semantics are induced by confluent LP-sl sterns, (2) there are many more transformation rules that lean to confluent LP-systems, (3) sema ntics induced by such systems can be used to model aggregation, (4) the new systems can be used to construct interesting counterexamples to some conje ctures about the space of well-behaved semantics. (C) 2001 Elsevier Science B.V. All rights reserved.