New decidable upper bound of the second level in the Straubing-Thérien concatenation hierarchy of star-free languages
Authors | |
---|---|
Year of publication | 2010 |
Type | Article in Periodical |
Magazine / Source | Discrete Mathematics & Theoretical Computer Science |
MU Faculty or unit | |
Citation | ALMEIDA, Jorge and Ondřej KLÍMA. New decidable upper bound of the second level in the Straubing-Thérien concatenation hierarchy of star-free languages. Discrete Mathematics & Theoretical Computer Science. France: DMTCS, 2010, vol. 12, No 4, p. 41-58. ISSN 1365-8050. |
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: |