Undecidable questions related to Church-Rosser Thue systems

DOI10.1016/0304-3975(83)90039-7zbMath0512.03019MaRDI QIDQ1839249

Colm P. O'Dunlaing

Publication date: 1983

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

Full work available at URL: https://doi.org/10.1016/0304-3975(83)90039-7

zbMATH Keywords

finite Thue systems; almost confluent; Church-Rosser congruence; preperfect

Mathematics Subject Classification ID

03D03: Thue and Post systems, etc.

Related Items

Finite complete rewriting systems and the complexity of word problem, Homogeneous Thue systems and the Church-Rosser property, Thue systems as rewriting systems, Church-Rosser controlled rewriting systems and equivalence problems for deterministic context-free languages, When is an extension of a specification consistent? Decidable and undecidable cases, Some properties of finite special string-rewriting systems, A field guide to equational logic, On the Knuth-Bendix completion for concurrent processes, Relating rewriting techniques on monoids and rings: congruences on monoids and ideals in monoid rings, Undecidable properties of monoids with word problem solvable in linear time., Cancellativity in finitely presented semigroups, Lambda-confluence for context rewriting systems, On reduced thue systems, A note on thue systems with a single defining relation

Cites Work

• Unnamed Item
• Unnamed Item
• Recursive unsolvability of group theoretic problems
• Homogeneous Thue systems and the Church-Rosser property
• Testing for the Church-Rosser property
• Thue congruences and the Church-Rosser property
• Monadic Thue systems
• Infinite regular Thue systems
• Confluent and Other Types of Thue Systems
• Recursive Unsolvability of a problem of Thue