| HAL-Inria | Publications, software ... of Inria's scientists |
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.
Cited literature [18 references]
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
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)