New decidable upper bound of the second level in the Straubing-Therien concatenation hierarchy of star-free languages - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics and Theoretical Computer Science Année : 2010

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

Résumé

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.
Fichier principal
Vignette du fichier
1463-5646-1-PB.pdf (189.64 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00990443 , version 1 (13-05-2014)

Identifiants

Citer

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

Collections

TDS-MACS
106 Consultations
764 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More