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

Investor logo

Warning

This publication doesn't include Faculty of Sports Studies. It includes Faculty of Science. Official publication website can be found on muni.cz.
Authors

ALMEIDA Jorge KLÍMA Ondřej

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

Faculty of Science

Citation
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