𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Total Termination of Term Rewriting is Undecidable

✍ Scribed by Hans Zantema

Publisher
Elsevier Science
Year
1995
Tongue
English
Weight
537 KB
Volume
20
Category
Article
ISSN
0747-7171

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Omega-Termination is Undecidable for Tot
Omega-Termination is Undecidable for Totally Terminating Term Rewriting Systems
✍ Alfons Geser πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 601 KB

We give a complete proof of the fact that the following problem is undecidable: Given: A term rewriting system, where the termination of its rewrite relation is provable by a total reduction order on ground terms, Wanted: Does there exist a strictly monotonic interpretation in the positive integers

Termination of term rewriting: interpret
Termination of term rewriting: interpretation and type elimination
✍ H. Zantema πŸ“‚ Article πŸ“… 1994 πŸ› Elsevier Science 🌐 English βš– 886 KB

We investigate proving termination of term rewriting systems by interpretation of terms in a well-founded monotone algebra. The well-known polynomial interpretations can be considered as a particular case in this framework. A classification of types of termination, including simple termination, is p