𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Undecidable properties of flat term rewrite systems

✍ Scribed by Guillem Godoy; Hugo Hernández

Book ID
105867547
Publisher
Springer
Year
2009
Tongue
English
Weight
234 KB
Volume
20
Category
Article
ISSN
0938-1279

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