zbMATH — the first resource for mathematics

A general theorem on termination of rewriting. (English) Zbl 1095.68046
Marcinkowski, Jerzy (ed.) et al., Computer science logic. 18th international workshop, CSL 2004, 13th annual conference of the EACSL, Karpacz, Poland, September 20–24, 2004. Proceedings. Berlin: Springer (ISBN 3-540-23024-6/pbk). Lecture Notes in Computer Science 3210, 100-114 (2004).
Summary: We re-express our theorem on the strong-normalisation of display calculi as a theorem about the well-foundedness of a certain ordering on first-order terms, thereby allowing us to prove the termination of systems of rewrite rules. We first show how to use our theorem to prove the well-foundedness of the lexicographic ordering, the multiset ordering and the recursive path ordering. Next, we give examples of systems of rewrite rules which cannot be handled by these methods but which can be handled by ours. Finally, we show that our method can also prove the termination of the Knuth-Bendix ordering and of dependency pairs.
For the entire collection see [Zbl 1060.68004].

68Q42 Grammars and rewriting systems
Full Text: DOI