![Sample our Mathematics & Statistics journals, sign in here to start your FREE access for 14 days]({"type":"image" , "src" : "/sda/5943/TOC-Subject-Sample-2021-Mathematics-Statistics.jpg"})
ABSTRACT
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 and
. Next we turn to concatenation hierarchies. It was shown by Straubing that the n-th level
of the dot-depth hierarchy is the variety
, where
is the variety of locally trivial semigroups and
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.
ACKNOWLEDGMENTS
The authors would like to thank Ben Steinberg and the anonymous referee for their many suggestions, which led to a significant improvement of the paper.
Notes
Work supported by the INTAS project 1224.
The word “subword” is used to mean a subsequence, not a segment.
In fact is a semigroup isomorphic to
(resp.
)