Undecidable questions related to Church-Rosser Thue systems
From MaRDI portal
Publication:1839249
DOI10.1016/0304-3975(83)90039-7zbMath0512.03019OpenAlexW1997017650MaRDI QIDQ1839249
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
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
