On deciding the confluence of a finite string-rewriting system on a given congruence class
From MaRDI portal
Publication:1102946
DOI10.1016/0022-0000(87)90017-1zbMath0645.03033OpenAlexW2058267787MaRDI QIDQ1102946
Publication date: 1987
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(87)90017-1
Free semigroups, generators and relations, word problems (20M05) Word problems, etc. in computability and recursion theory (03D40) Theory of computing (68Q99) Thue and Post systems, etc. (03D03)
Related Items (14)
The problem of deciding confluence on a given congruence class is tractable for finite special string-rewriting systems ⋮ It is decidable whether a monadic thue system is canonical over a regular set ⋮ A polynomial algorithm testing partial confluence of basic semi-Thue systems ⋮ Some decision problems about controlled rewriting systems ⋮ About the descriptive power of certain classes of finite string-rewriting systems ⋮ Decision problems for finite special string-rewriting systems that are confluent on some congruence class ⋮ Completing a finite special string-rewriting system on the congruence class of the empty word ⋮ On weakly confluent monadic string-rewriting systems ⋮ Some properties of finite special string-rewriting systems ⋮ The pre-NTS property is undecidable for context-free grammars ⋮ A polynomial algorithm testing partial confluence of basic semi-Thue systems ⋮ Using string-rewriting for solving the word problem for finitely presented groups ⋮ \(L(A)=L(B)\)? decidability results from complete formal systems ⋮ Lambda-confluence for context rewriting systems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The equation \(a_ M=b^ Nc^ P\) in a free group
- Finite complete rewriting systems and the complexity of word problem
- An \(O(| T| ^ 3)\) algorithm for testing the Church-Rosser property of Thue systems
- Some undecidability results for non-monadic Church-Rosser Thue systems
- A note on a special one-rule semi-Thue system
- A finite Thue system with decidable word problem and without equivalent finite canonical system
- Complexity of certain decision problems about congruential languages
- Testing for the Church-Rosser property
- Monadic Thue systems
- An improvement on Valiant's decision procedure for equivalence of deterministic finite turn pushdown machines
- Cancellativity in finitely presented semigroups
- Infinite regular Thue systems
- On theories with a combinatorial definition of 'equivalence'
- On Proving Uniform Termination and Restricted Termination of Rewriting Systems
- A note on thue systems with a single defining relation
- Finite canonical rewriting systems for congruences generated by concurrency relations
- Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
- Confluent and Other Types of Thue Systems
- A note on special thue systems with a single defining relation
- The equivalence problem for deterministic finite-turn pushdown automata
This page was built for publication: On deciding the confluence of a finite string-rewriting system on a given congruence class
