𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The undecidability of self-embedding for term rewriting systems

✍ Scribed by David A. Plaisted

Book ID
113162791
Publisher
Elsevier Science
Year
1985
Tongue
English
Weight
306 KB
Volume
20
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Reachability and confluence are undecida
Reachability and confluence are undecidable for flat term rewriting systems
✍ Florent Jacquemard πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 99 KB

Ground reachability, ground joinability and confluence are shown undecidable for flat term rewriting systems, i.e., systems in which all left and right members of rule have depth at most one.

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