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

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:	Institute for Theoretical Computer Science Mathematical structures and their physical applications Algebraic Methods in Automata and Formal Language Theory II