The Wreath Product Principle for Ordered Semigroups

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 V n LI, where LI is the variety of locally trivial semigroups and V n is the n-th level of the Straubing-Therien 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-Therien hierarchy is decidable. 1 Introduction All semigroups and monoids considered in t..