Informace o publikaci

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

Logo poskytovatele
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