A Semantic Approach to Order-sorted Rewriting

✍ Scribed by A. Werner

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 863 KB
• Volume: 25
• Category: Article
• ISSN: 0747-7171
• DOI: 10.1006/jsco.1997.0188

✦ Synopsis

Order-sorted rewriting builds a nice framework to handle partially defined functions and subtypes. To be able to prove a critical-pair lemma and Birkhoff's completeness theorem, order-sorted rewriting was restricted to sort decreasing term rewriting systems. However, natural examples show that this approach is too restrictive.

To solve this problem, we generalize well-sorted terms to semantically well-sorted terms and well-sorted substitutions to a restricted form of semantically well-sorted substitutions. Semantically well-sorted terms with respect to a set of equations E are terms that denote well-defined elements in every algebra satisfying E.

We prove a critical-pair lemma and Birkhoff's completeness theorem for so-called range-unique signatures and arbitrary order-sorted rewriting systems. A transformation is given which allows us to obtain an equivalent range-unique signature from each nonrange-unique one. We also show decidability and undecidability results.