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

Logo poskytovatele

Varování

Publikace nespadá pod Fakultu sportovních studií, 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:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.

Další info