Inverse monoids and rational Schreier subsets of the free group. (English) Zbl 0757.20017

A Schreier subset of the free group \(FG(X)\) is a subset \(L\) of \(FG(X)\) which contains the identity element and which contains every prefix of the reduced word of each element of \(L\). If \(M\) is an inverse monoid presented by the set \(X\) of generators and a set \(T=\{(e_ i,f_ i): i\in I\}\) of relations where \(e_ i,f_ i\) are idempotents of the free inverse monoid \(\text{FIM}(X)\), then the natural homomorphism \(\sigma\) of \(M\) onto its greatest group homomorphic image \(FG(X)\) embeds each \(\mathcal R\)-class \(R\) of \(M\) into \(FG(X)\) and \(R\sigma\) is a Schreier subset of \(FG(X)\). In this case \(R\sigma\) is said to be naturally associated with \(\text{FIM}(X)\). Such Schreier subsets \(L\) of \(FG(X)\) are characterized in the main theorem of this paper, in terms of a finite test tree for the subtree of the Cayley graph \(\Gamma(X)\) of \(FG(X)\) whose vertices are labeled by the elements of \(L\). If \(I\) is finite, then \(R\sigma\) is a rational subset of \(FG(X)\), but not every rational Schreier subset of \(FG(X)\) is obtained in this way. Every rational Schreier subset of \(FG(X)\), with \(X\) finite, whose associated subtree of \(\Gamma(X)\) contains only a finite number of negatively labeled edges, is naturally associated with \(\text{FIM}(X)\).


20M05 Free semigroups, generators and relations, word problems
20M18 Inverse semigroups
20M35 Semigroups in automata theory, linguistics, etc.
20E05 Free nonabelian groups
Full Text: DOI EuDML


[1] Benois, M.,Parties rationnelles du groupe libre, C. R. Acad Sci. Paris, Sér. A.269 (1969), 1188–1190. · Zbl 0214.03903
[2] Berstel, J.,Transductions and context-free languages, Teubner Stüdienbucher, 1979. · Zbl 0424.68040
[3] Hopcroft, J. E. and J. D. Ullman,Formal languages and their relation to automata, Addison-Wesley, 1969. · Zbl 0196.01701
[4] Lallement, G.,Semigroups and Combinatorial Applications, Wiley, 1979. · Zbl 0421.20025
[5] Margolis, S. and J. Meakin,E-unitary Inverse Monoids and the Cayley Graph of a Group Presentation, J. Pure Appl. Algebra58 (1989). · Zbl 0676.20037
[6] Margolis, S. and Meakin,Inverse monoids, trees and context-free languages, Trans. Amer. Math. Soc. (to appear). · Zbl 0795.20043
[7] Margolis, S. and J. Meakin,Some decision problems for inverse monoid presentations, in ”Semigroups and their applications”, Goberstein, Higgins (Ed.), D. Riedel, 1987, 99–110.
[8] Munn, W. D.,Free inverse semigroups, Proc. Lond. Math. Soc.30 (1974), 385–404. · Zbl 0305.20033 · doi:10.1112/plms/s3-29.3.385
[9] Petrich, M.,Inverse Semigroups, Wiley, 1984. · Zbl 0546.20053
[10] Pin, J. E.,Variétés de languages formels, Masson, 1984.
[11] Rabin, M. O.,Decidability of second order theories and automata on infinite trees, Trans. Amer. Math. Soc.141 (1969), 1–35. · Zbl 0221.02031
[12] Rabin, M. O.,Automata on infinite objects and Church’s problem, C.B.M.S. Regional Conf. Series in Math., No. 14 (1971), Amer. Math. Soc.. · Zbl 0231.02056
[13] Serre, J. P.,Trees, Springer, Berlin, 1980. · Zbl 0548.20018
[14] Stephen, J. B.,Presentations of inverse monoids, J. Pure. Appl. Algebra63 (1990), no. 1, 81–112. · Zbl 0691.20044 · doi:10.1016/0022-4049(90)90057-O
[15] Stephen, J.B.,Applications of automata theory to presentations of monoids and inverse monoids, Ph.D. Thesis, University of Nebraska, 1987.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.