Omega-Termination is Undecidable for Totally Terminating Term Rewriting Systems

✍ Scribed by Alfons Geser

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 601 KB
• Volume: 23
• Category: Article
• ISSN: 0747-7171
• DOI: 10.1006/jsco.1996.0095

✦ Synopsis

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 that proves termination?