Pin, Jean-Eric; Weil, Pascal The wreath product principle for ordered semigroups. (English) Zbl 1017.06008 Commun. Algebra 30, No. 12, 5677-5713 (2002). A class \(\mathcal L\) of semigroup languages closed under finite joins, finite meets, inverse homomorphisms and factors is called a positive variety of languages. New definitions of recognition of languages by ordered semigroups, by ordered transformation semigroups and by ordered deterministic automata are presented and investigated. For a variety \(\mathbf V\) of ordered semigroups, let \(\mathcal L(\mathbf V)\) be the least positive variety of languages containing all languages recognized by an ordered semigroup from \(\mathbf V\). A version of the Eilenberg theorem – \(\mathcal L\) is a bijection preserving inclusion – is proved. The wreath product principle is generalized for ordered semigroups and as a consequence the positive varieties of languages corresponding to the ordered semigroup varieties \(\mathbf J_1^{+}\star \mathbf V\), \(\mathbf J^{+}\star \mathbf V\), \(\mathbf D_1\star \mathbf V\), and \(\mathbf D \star \mathbf V\) are described, where \(\mathbf J^{+}\) is the variety of ordered monoids such that \(1\) is the greatest element, \(\mathbf J^{+}_1\) is the subvariety of \(\mathbf J^{+}\)consisting of all semilattices, \(\mathbf D_1\) is the variety of ordered right-zero semigroups, \(\mathbf D\) is the least variety containing \(\mathbf D_1\) and closed under semidirect products, and \(\mathbf V\) is variety of ordered semigroups which is not a variety of groups. Finally, the Straubing theorem connecting the dot-depth hierarchy with the concatenation hierarchy is strenghtened to half levels. Reviewer: Václav Koubek (Praha) Cited in 1 ReviewCited in 18 Documents MSC: 06F05 Ordered semigroups and monoids 68Q70 Algebraic theory of languages and automata 20M35 Semigroups in automata theory, linguistics, etc. Keywords:variety of recognizable languages; variety of finite ordered semigroups; wreath product of semigroups; testable language; dot-depth hierarchy PDFBibTeX XMLCite \textit{J.-E. Pin} and \textit{P. Weil}, Commun. Algebra 30, No. 12, 5677--5713 (2002; Zbl 1017.06008) Full Text: DOI