On the Complexity of Computing the Profinite Closure of a Rational Language - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Theoretical Computer Science Année : 2011

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

Résumé

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

Dates et versions

hal-00641554 , version 1 (16-11-2011)

Identifiants

Citer

Pierre-Cyrille Heam. On the Complexity of Computing the Profinite Closure of a Rational Language. Theoretical Computer Science, 2011, 412 (41), pp.5808-5813. ⟨10.1016/j.tcs.2011.06.022⟩. ⟨hal-00641554⟩
113 Consultations
181 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More