Loading [MathJax]/extensions/MathZoom.js
The wreath product principle for ordered semigroups
Pin, Jean-Eric ; Weil, Pascal
HAL, hal-00112618 / Harvested from HAL
Straubing's wreath product principle provides a description of the languages recognized by the wreath product of two monoids. A similar principle for ordered semigroups is given in this paper. Applications to language theory extend standard results of the theory of varieties to positive varieties. They include a characterization of positive locally testable languages and syntactic descriptions of the operations L ? La and L ? LaA*. Next we turn to concatenation hierarchies. It was shown by Straubing that the n-th level Bn of the dot-depth hierarchy is the variety Vn * LI, where LI is the variety of locally trivial semigroups and Vn is the n-th level of the Straubing-Thérien hierarchy. We prove that a similar result holds for the half levels. It follows in particular that a level or a half level of the dot-depth hierarchy is decidable if and only if the corresponding level of the Straubing-Thérien hierarchy is decidable.
Publié le : 2002-07-05
Classification:  semigroup,  wreath product,  finite automata,  regular language,  MR 06F05 (20M07 20M35),  [MATH.MATH-GR]Mathematics [math]/Group Theory [math.GR],  [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
@article{hal-00112618,
     author = {Pin, Jean-Eric and Weil, Pascal},
     title = {The wreath product principle for ordered semigroups},
     journal = {HAL},
     volume = {2002},
     number = {0},
     year = {2002},
     language = {en},
     url = {http://dml.mathdoc.fr/item/hal-00112618}
}
Pin, Jean-Eric; Weil, Pascal. The wreath product principle for ordered semigroups. HAL, Tome 2002 (2002) no. 0, . http://gdmltest.u-ga.fr/item/hal-00112618/