![Důležité termíny](https://cdn.muni.cz/media/3633704/image_2.jpg?mode=crop¢er=0.5,0.5&rnd=133572412150000000&heightratio=0.5&width=278)
Informace o publikaci
New decidable upper bound of the second level in the Straubing-Thérien concatenation hierarchy of star-free languages
Autoři | |
---|---|
Rok publikování | 2010 |
Druh | Článek v odborném periodiku |
Časopis / Zdroj | Discrete Mathematics & Theoretical Computer Science |
Fakulta / Pracoviště MU | |
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: |