Parikh-reducing Church-Rosser representations for some classes of regular languages (Q1676318): Difference between revisions

A language is said to be Church-Rosser congruential if it is the union of finitely many classes of the congruence defined by a finite length-reducing Church-Rosser rewriting system. \textit{R. McNaughton} et al. [J. Assoc. Comput. Mach. 35, No. 2, 324--344 (1988; Zbl 0652.68093)], who introduced the concept, asked whether every regular language is Church-Rosser congruential. A positive answer was given by \textit{V. Diekert} et al. [Lect. Notes Comput. Sci. 7392, 177--188 (2012; Zbl 1367.68166)] by proving a stronger result: for any regular language \(L\) over an alphabet \(A\) and any given weight function \(A \rightarrow \mathbb{Z}_{+}\), there is a finite weight-reducing Church-Rosser rewriting system for which \(L\) is congruential. The proof makes essential use of local divisors of monoids (cf. [\textit{V. Diekert} and \textit{M. Kufleitner}, Theor. Comput. Sci. 610, Part A, 13--23 (2016; Zbl 1332.68147)] for a survey of the local divisor technique). In this paper the class of rewriting systems considered is further restricted. The author calls a rewriting system Parikh-reducing if it is weight-reducing for every weight function. The main result is that if all groups in the syntactic monoid of a regular language are abelian, then the language has a congruential representation by a finite Parikh-reducing Church-Rosser rewriting system. Moreover, the groups in the monoid presented by this rewriting system are also abelian. Secondly, the regular group languages over a two-letter alphabet are also shown to have such representations. Finally, the author considers the sizes of the monoids presented by the rewriting systems constructed. The local divisor technique is used in this work, too.