𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Some undecidable termination problems for semi-Thue systems

✍ Scribed by Géraud Sénizergues

Publisher
Elsevier Science
Year
1995
Tongue
English
Weight
822 KB
Volume
142
Category
Article
ISSN
0304-3975

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

Some Non-Recursive Classes of Thue Syste
Some Non-Recursive Classes of Thue Systems With Solvable Word Problem
✍ Ann Yasuhara 📂 Article 📅 1974 🏛 John Wiley and Sons 🌐 English ⚖ 863 KB

We take as our general setting decision problems regarding certain combinatorial properties of THUE systems and algebraic properties of the semi-groups they present. Let the class of all THUE systems be divided up as follows: V o = {all THUE systems with unsolvable word problem}, Wl = {all THUE sys