Parikh-reducing Church-Rosser representations for some classes of regular languages (Q1676318)

From MaRDI portal
Revision as of 04:17, 5 March 2024 by Import240304020342 (talk | contribs) (Set profile property.)
scientific article
Language Label Description Also known as
English
Parikh-reducing Church-Rosser representations for some classes of regular languages
scientific article

    Statements

    Parikh-reducing Church-Rosser representations for some classes of regular languages (English)
    0 references
    0 references
    6 November 2017
    0 references
    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.
    0 references
    rewriting system
    0 references
    Church-Rosser
    0 references
    Parikh-reducing
    0 references
    regular language
    0 references
    congruential language
    0 references
    syntactic monoid
    0 references
    local divisor
    0 references

    Identifiers