An almost-confluent congruential language which is not Church-Rosser congruential (Q2346383)

Each regular language~\(L\) is almost-confluent congruential, and it was recently shown [\textit{V. Diekert} et al., Lect. Notes Comput. Sci. 7392, 177--188 (2012; Zbl 1367.68166)] that \(L\) is also Church-Rosser congruential. Since each Church-Rosser congruential language is trivially also almost-confluent congruential, this leaves open the question whether there are languages that are almost-confluent congruential, but not Church-Rosser congruential. Known complexity arguments suggest that such languages exist, but this note establishes such a language directly and thus solves the open problem. A language \(L \subseteq \Sigma^*\) is congruential if there exists a congruence \(\mathord{\cong} \subseteq \Sigma^* \times \Sigma^*\) on the set of strings such that \(L\) is the union of a finite number of congruence classes. In particular, the congruence~\(\cong\) can be generated by a (variable-free) string rewrite system \(T\), which is simply a finite set of pairs of strings (called rules). Each rule is applied to a string~\(w\) by replacing in \(w\) an occurrence of one of the rule strings by the other rule string. In the congruence~\(\cong_T\) induced by~\(T\) two strings are congruent if and only if one string can be rewritten into the other using only the rules of \(T\). The properties `almost-confluent' and `Church-Rosser' apply to the string rewrite system \(T\). It is Church-Rosser if all congruent strings can be rewritten to a common string using only length-reducing rewrites (i.e., rule applications in which the replaced string is longer than the replacement). Given the string rewrite system \(T\), we let \(T_{\mathord=}\) be the string rewrite system that contains exactly those rules of \(T\) that contain strings of equal length. Let us call strings that are congruent for~\(T_{\mathord=}\) strictly congruent. The string rewrite system~\(T\) is almost-confluent if all congruent strings (for \(T\)) can be reduced to strictly congruent strings (for \(T_{\mathord=}\)) using only length-reducing rewrites. Clearly, each Church-Rosser string rewrite system is also almost-confluent, and the inclusion is strict as demonstrated in this note. The note shortly recalls the relevant notions and then directly proves the main statement by exhibiting a language that is almost-confluent congruential, but not Church-Rosser congruential. The proofs for those statements can easily be appreciated by anyone with basic mathematical skills.