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

Varování

Publikace nespadá pod Ústav výpočetní techniky, ale pod Přírodovědeckou fakultu. Oficiální stránka publikace je na webu muni.cz.

Autoři	ALMEIDA Jorge KLÍMA Ondřej
Rok publikování	2010
Druh	Článek v odborném periodiku
Časopis / Zdroj	Discrete Mathematics & Theoretical Computer Science
Fakulta / Pracoviště MU	Přírodovědecká fakulta
Citace
Obor	Obecná matematika
Klíčová slova	formal languages; regular languages; concatenation hierarchies; level two; star-free languages
Popis	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.
Související projekty:	Institut Teoretické Informatiky Matematické struktury a jejich fyzikální aplikace Algebraické metody v teorii automatů a formálních jazyků II