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.03033MaRDI 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
20M05: Free semigroups, generators and relations, word problems
03D40: Word problems, etc. in computability and recursion theory
68Q99: Theory of computing
03D03: Thue and Post systems, etc.
Related Items
Using string-rewriting for solving the word problem for finitely presented groups, On weakly confluent monadic string-rewriting 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, A polynomial algorithm testing partial confluence of basic semi-Thue systems, Completing a finite special string-rewriting system on the congruence class of the empty word, Some properties of finite special string-rewriting systems, The pre-NTS property is undecidable for context-free grammars, \(L(A)=L(B)\)? decidability results from complete formal systems, It is decidable whether a monadic thue system is canonical over a regular set, The problem of deciding confluence on a given congruence class is tractable for finite special string-rewriting systems
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
