Publication details

New decidable upper bound of the second level in the Straubing-Thérien concatenation hierarchy of star-free languages

Investor logo


Year of publication 2010
Type Article in Periodical
Magazine / Source Discrete Mathematics & Theoretical Computer Science
MU Faculty or unit

Faculty of Science

Field General mathematics
Keywords formal languages; regular languages; concatenation hierarchies; level two; star-free languages
Description 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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.

More info