Some undecidability results for non-monadic Church-Rosser Thue systems
From MaRDI portal
Publication:1057264
DOI10.1016/0304-3975(84)90090-2zbMath0563.03019OpenAlexW1998439085MaRDI QIDQ1057264
Publication date: 1984
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(84)90090-2
Undecidability and degrees of sets of sentences (03D35) Decidability of theories and sets of sentences (03B25) Thue and Post systems, etc. (03D03)
Related Items (19)
On sufficient-completeness and related properties of term rewriting systems ⋮ The problems of cyclic equality and conjugacy for finite complete rewriting systems ⋮ Codes modulo finite monadic string-rewriting systems ⋮ Weights for total division orderings on strings ⋮ Restrictions of congruences generated by finite canonical string-rewriting systems ⋮ Thue systems as rewriting systems ⋮ On deciding the confluence of a finite string-rewriting system on a given congruence class ⋮ An efficient algorithm to decide whether a monoid presented by a regular Church-Rosser Thue system is a group ⋮ Some decision problems about controlled rewriting systems ⋮ Decision problems for finite special string-rewriting systems that are confluent on some congruence class ⋮ Commutativity in groups presented by finite Church-Rosser Thue systems ⋮ When is an extension of a specification consistent? Decidable and undecidable cases ⋮ On weakly confluent monadic string-rewriting systems ⋮ Cancellation rules and extended word problems ⋮ A strong geometric hyperbolicity property for directed graphs and monoids. ⋮ Some undecidability results concerning the property of preserving regularity ⋮ Lambda-confluence for context rewriting systems ⋮ On two problems related to cancellativity ⋮ On deciding whether a monoid is a free monoid or is a group
Cites Work
- Decidable sentences of Church-Rosser congruences
- Monadic Thue systems
- When is a monoid a group? The Church-Rosser case is tractable
- Infinite regular Thue systems
- Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
- Confluent and Other Types of Thue Systems
- The honest subrecursive classes are a lattice
- Machine Configuration and Word Problems of Given Degree of Unsolvability
- FINITELY PRESENTED GROUP WHOSE WORD PROBLEM HAS THE SAME DEGREE AS THAT OF AN ARBITRARILY GIVEN THUE SYSTEM (AN APPLICATION OF METHODS OF BRITTON)
- Strong Computability and Variants of the Uniform Halting Problem
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Some undecidability results for non-monadic Church-Rosser Thue systems
