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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/hal-00641554
Contributor : Pierre-Cyrille Heam <>
Submitted on : Wednesday, November 16, 2011 - 10:31:54 AM
Last modification on : Friday, April 12, 2019 - 10:18:03 AM
Long-term archiving on : Friday, February 17, 2012 - 2:25:12 AM

File

PROBINFheam.pdf
Files produced by the author(s)

Identifiers

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⟩

Share

Metrics

Record views

304

Files downloads

185