×

The wreath product principle for ordered semigroups. (English) Zbl 1017.06008

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.

MSC:

06F05 Ordered semigroups and monoids
68Q70 Algebraic theory of languages and automata
20M35 Semigroups in automata theory, linguistics, etc.
PDFBibTeX XMLCite
Full Text: DOI