Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, Epiciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
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 Connect in order to contact the contributor
Submitted on : Tuesday, May 13, 2014 - 3:37:14 PM
Last modification on : Friday, April 22, 2022 - 11:42:04 AM
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

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, Vol. 12 no. 4 (4), pp.41-58. ⟨10.46298/dmtcs.490⟩. ⟨hal-00990443⟩

Share

Metrics

Record views

100

Files downloads

598