On deciding the confluence of a finite string-rewriting system on a given congruence class (Q1102946)

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.