Jorge Almeida ; Ondrej Klima - New decidable upper bound of the second level in the Straubing-Therien concatenation hierarchy of star-free languages

dmtcs:490 - Discrete Mathematics & Theoretical Computer Science, January 1, 2010, Vol. 12 no. 4 - https://doi.org/10.46298/dmtcs.490
New decidable upper bound of the second level in the Straubing-Therien concatenation hierarchy of star-free languagesArticle

Authors: Jorge Almeida 1; Ondrej Klima 2

  • 1 Departamento de Matemática [Porto]
  • 2 Department of Mathematics and Statistics [Btno]

In a recent paper we gave a counterexample to a longstanding conjecture concerning the characterization of regular languages of level 2 in the Straubing-Therien 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.


Volume: Vol. 12 no. 4
Published on: January 1, 2010
Imported on: March 26, 2015
Keywords: formal languages,regular languages,concatenation hierarchies,level two,star-free languages,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

1 Document citing this article

Consultation statistics

This page has been seen 416 times.
This article's PDF has been downloaded 314 times.