Skip to Main content Skip to Navigation
Journal articles

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

Abstract : 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.
Document type :
Journal articles
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download

https://hal.inria.fr/hal-00990443
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Tuesday, May 13, 2014 - 3:37:14 PM
Last modification on : Wednesday, November 18, 2020 - 6:32:03 PM
Long-term archiving on: : Monday, April 10, 2017 - 10:26:23 PM

File

1463-5646-1-PB.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00990443, version 1

Collections

Citation

Jorge Almeida, Ondrej Klima. New decidable upper bound of the second level in the Straubing-Therien concatenation hierarchy of star-free languages. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2010, 12 (4), pp.41-58. ⟨hal-00990443⟩

Share

Metrics

Record views

275

Files downloads

939