The undecidability of self-embedding for finite semi-Thue and Thue systems

DOI10.1016/0304-3975(86)90148-9zbMath0624.03032OpenAlexW1976203892MaRDI QIDQ1092041

Friedrich Otto

Publication date: 1986

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(86)90148-9

zbMATH Keywords

semi-Thue systemDLBA-emptiness problemself-embedding problem

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Word problems, etc. in computability and recursion theory (03D40) Thue and Post systems, etc. (03D03)

Related Items (2)

Non-Looping String Rewriting ⋮ One-rule semi-Thue systems with loops of length one, two or three

Cites Work

• Orderings for term-rewriting systems
• The undecidability of the preperfectness of Thue systems
• The undecidability of self-embedding for term rewriting systems
• Unnamed Item

This page was built for publication: The undecidability of self-embedding for finite semi-Thue and Thue systems