On deciding the confluence of a finite string-rewriting system on a given congruence class
A string-rewriting system R on alphabet \(\Sigma\) induces a congruence \(\leftrightarrow^{*}_{R}\) on the set of strings \(\Sigma^*\). If R is finite, Noetherian, and confluent, the reduction relation \(\to^{*}_{R}\) induced by R can be used to effectively decide this congruence, i.e., to solve the word problem for the monoid presented by (\(\Sigma\) ;R) [cf., e.g., \textit{R. V. Book}, J. Symb. Comput. 3, 39-68 (1987; Zbl 0638.68091)]. The system R is called confluent on a congruence class \([w]_ R\) if every two strings \(u,v\in [w]_ R\) have a common descendant modulo \(\to^{*}_{R}\). If R is finite, and Noetherian, then confluence on \([w]_ R\) implies that the membership problem for \([w]_ R\) is decidable. For example, Dehn's algorithm for the word problem [cf., e.g., \textit{R. C. Lyndon} and \textit{P. E. Schupp}: Combinatorical group theory (1977; Zbl 0368.20023)] can be seen as exploiting this fact. In the present paper the following decision problem CCC is being investigated: INSTANCE: A finite string-rewriting system R on \(\Sigma\), and a string \(w\in \Sigma^*\). QUESTION: Is R confluent on \([w]_ R?\) As it turns out, this problem is undecidable in general even for finite, length-reducing string-rewriting systems. On the other hand, using a characterization theorem it is shown that this problem is decidable for finite monadic string-rewriting systems. However, the given upper bound for this algorithm is doubly exponential. Finally, more restricted versions of the problem CCC are investigated.
- Some results on Green's relations for monoids presented by monadic string-rewriting systems
- The problem of deciding confluence on a given congruence class is tractable for finite special string-rewriting systems
- Decision problems for finite special string-rewriting systems that are confluent on some congruence class
- scientific article; zbMATH DE number 789389
- scientific article; zbMATH DE number 177883
- On weakly confluent monadic string-rewriting systems
- Infinite convergent string-rewriting systems and cross-sections for finitely presented monoids
- Some properties of finite special string-rewriting systems
- The word matching problem is undecidable for finite special string-rewriting systems that are confluent
- Reachability in Unions of Commutative Rewriting Systems Is Decidable
- A finite Thue system with decidable word problem and without equivalent finite canonical system
- A note on a special one-rule semi-Thue system
- A note on special thue systems with a single defining relation
- A note on thue systems with a single defining relation
- An \(O(| T| ^ 3)\) algorithm for testing the Church-Rosser property of Thue systems
- An improvement on Valiant's decision procedure for equivalence of deterministic finite turn pushdown machines
- Cancellativity in finitely presented semigroups
- Complexity of certain decision problems about congruential languages
- Confluent and Other Types of Thue Systems
- Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
- Finite canonical rewriting systems for congruences generated by concurrency relations
- Finite complete rewriting systems and the complexity of word problem
- scientific article; zbMATH DE number 3836321 (Why is no real title available?)
- scientific article; zbMATH DE number 3811849 (Why is no real title available?)
- scientific article; zbMATH DE number 3898258 (Why is no real title available?)
- scientific article; zbMATH DE number 43246 (Why is no real title available?)
- scientific article; zbMATH DE number 3563392 (Why is no real title available?)
- scientific article; zbMATH DE number 3574107 (Why is no real title available?)
- scientific article; zbMATH DE number 3299786 (Why is no real title available?)
- Infinite regular Thue systems
- Monadic Thue systems
- On Proving Uniform Termination and Restricted Termination of Rewriting Systems
- On theories with a combinatorial definition of 'equivalence'
- Some undecidability results for non-monadic Church-Rosser Thue systems
- Testing for the Church-Rosser property
- The equation \(a_ M=b^ Nc^ P\) in a free group
- The equivalence problem for deterministic finite-turn pushdown automata
- Complexity of certain decision problems about congruential languages
- A polynomial algorithm testing partial confluence of basic semi-Thue systems
- When is an extension of a specification consistent? Decidable and undecidable cases
- 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
- On deciding confluence of finite string-rewriting systems modulo partial commutativity
- \(L(A)=L(B)\)? decidability results from complete formal systems
- Lambda-confluence for context rewriting systems
- Algorithms and reductions for rewriting problems
- It is decidable whether a monadic thue system is canonical over a regular set
- Reducing the gradedness problem of string rewriting systems to a termination problem
- The problem of deciding confluence on a given congruence class is tractable for finite special string-rewriting systems
- scientific article; zbMATH DE number 177883 (Why is no real title available?)
- Infinite Families of Finite String Rewriting Systems and Their Confluence
- Restrictions of congruences generated by finite canonical string-rewriting systems
- A polynomial algorithm testing partial confluence of basic semi-Thue systems
- Lambda-confluence is undecidable for clearing restarting automata
- Using string-rewriting for solving the word problem for finitely presented groups
- On Simon's congruence closure of a string
- The Knuth-Bendix algorithm and the conjugacy problem in monoids.
- 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
This page was built for publication: On deciding the confluence of a finite string-rewriting system on a given congruence class
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1102946)
