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

✍ Scribed by Jürgen Dix; Mauricio Osorio; Claudia Zepeda

• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 236 KB
• Volume: 108
• Category: Article
• ISSN: 0168-0072
• DOI: 10.1016/s0168-0072(00)00044-0

✦ Synopsis

Recently, Brass and Dix showed (J. Automat. Reason. 20(1) (1998) 143-165) that the well founded semantics WFS can be deÿned as a con uent 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 Con uent LP-systems CS. Such a system CS is a rewriting system on the set of all logic programs over a ÿxed signature L 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 con uent LP-systems, (2) there are many more transformation rules that lead to con uent 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.