Undecidable questions related to Church-Rosser Thue systems

DOI10.1016/0304-3975(83)90039-7zbMath0512.03019OpenAlexW1997017650MaRDI 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 systemsalmost confluentChurch-Rosser congruencepreperfect

Mathematics Subject Classification ID

Thue and Post systems, etc. (03D03)

Related Items

An equational logic sampler ⋮ Restrictions of congruences generated by finite canonical string-rewriting systems ⋮ On reduced thue systems ⋮ Thue systems as rewriting systems ⋮ A note on thue systems with a single defining relation ⋮ Church-Rosser controlled rewriting systems and equivalence problems for deterministic context-free languages ⋮ On public-key cryptosystem based on Church-Rosser string-rewriting systems ⋮ Undecidable properties of monoids with word problem solvable in linear time. ⋮ 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 ⋮ Cancellativity in finitely presented semigroups ⋮ Finite complete rewriting systems and the complexity of word problem ⋮ Homogeneous Thue systems and the Church-Rosser property ⋮ Lambda-confluence for context rewriting systems

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