New decidable upper bound of the second level in the Straubing-Thérien concatenation hierarchy of star-free languages
Jorge Almeida, Ondrej Klíma
Abstract
In a recent paper we gave a counterexample to a longstanding
conjecture concerning the characterization of regular languages of
level 2 in the Straubing-Thérien concatenation hierarchy of star-free
languages. In that paper a new upper bound for the corresponding
pseudovariety of monoids was implicitly given. In this paper we show
that it is decidable whether a given monoid belongs to the new upper
bound. We also prove that this new upper bound is incomparable with
the previous upper bound.
Full Text: PDF PostScript