×

Free profinite \(\mathcal R\)-trivial monoids. (English) Zbl 0892.20035

The structure of the free profinite \(\mathcal R\)-trivial monoids is elucidated in this paper. If \(\mathbf V\) is a pseudovariety of finite monoids, the free pro-\(\mathbf V\) monoid over an alphabet \(A\) is the projective limit of the \(A\)-generated elements of \(\mathbf V\). The algebraic and topological structure of the free pro-\(\mathbf V\) monoids illuminates several questions on the class of rational languages recognized by monoids in \(\mathbf V\), and on the membership problem for pseudovarieties built from \(\mathbf V\) using such operations as joins, semidirect products and Mal’cev products. However, the structure of the free pro-\(\mathbf V\) monoids is known for relatively few values of \(\mathbf V\).
In this paper, two equivalent representations of the free pro-\(\mathbf R\) monoids are given, where \(\mathbf R\) is the pseudovariety of \(\mathcal R\)-trivial monoids. The first representation is in terms of labeled ordinals, or transfinite words, and it renders more adequately by algebraic properties of these monoids. The second one, in terms of labeled trees is more adapted to render their topological properties. The method is then extended to describe the structure of the free pro-\(\mathbf{DRH}\) monoids, where \(\mathbf H\) is a pseudovariety of groups and \(\mathbf{DRH}\) is the pseudovariety of all semigroups in which each regular \(\mathcal R\)-class is a group in \(\mathbf H\). These results are applied to the determination of the languages recognized by monoids in \(\mathbf{DRH}\) and to the computation of the join of \(\mathbf{DRH}\) and its right-left dual \(\mathbf{DLH}\).
Reviewer: P.Weil (Paris)

MSC:

20M05 Free semigroups, generators and relations, word problems
20M07 Varieties and pseudovarieties of semigroups
20M35 Semigroups in automata theory, linguistics, etc.
68Q70 Algebraic theory of languages and automata
08A70 Applications of universal algebra in computer science
08C15 Quasivarieties
PDFBibTeX XMLCite
Full Text: DOI