On the Complexity of Computing the Profinite Closure of a Rational Language

Pierre-Cyrille Heam 1, 2
2 CASSIS - Combination of approaches to the security of infinite states systems
FEMTO-ST - Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174), INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : The profinite topology is used in rational languages classification. In particular, several important decidability problems, related to the Malcev product, reduce to the computation of the closure of a rational language in the profinite topology. It is known that given a rational language by a deterministic automaton, computing a deterministic automaton accepting its profinite closure can be done with an exponential upper bound. This paper is dedicated the study of a lower bound for this problem: we prove that in some cases, if the alphabet contains at least three letters, it requires an exponential time.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2011, 412 (41), pp.5808-5813. 〈http://www.sciencedirect.com/science/article/pii/S0304397511005494〉. 〈10.1016/j.tcs.2011.06.022〉
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00641554
Contributeur : Pierre-Cyrille Heam <>
Soumis le : mercredi 16 novembre 2011 - 10:31:54
Dernière modification le : vendredi 6 juillet 2018 - 15:06:10
Document(s) archivé(s) le : vendredi 17 février 2012 - 02:25:12

Fichier

PROBINFheam.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Pierre-Cyrille Heam. On the Complexity of Computing the Profinite Closure of a Rational Language. Theoretical Computer Science, Elsevier, 2011, 412 (41), pp.5808-5813. 〈http://www.sciencedirect.com/science/article/pii/S0304397511005494〉. 〈10.1016/j.tcs.2011.06.022〉. 〈hal-00641554〉

Partager

Métriques

Consultations de la notice

255

Téléchargements de fichiers

103