Skip to Main content Skip to Navigation
New interface
Journal articles

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 Nancy - Grand Est, LORIA - FM - Department of Formal Methods
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 metadata

Cited literature [17 references]  Display  Hide  Download
Contributor : Pierre-Cyrille Heam Connect in order to contact the contributor
Submitted on : Wednesday, November 16, 2011 - 10:31:54 AM
Last modification on : Friday, January 21, 2022 - 3:08:57 AM
Long-term archiving on: : Friday, February 17, 2012 - 2:25:12 AM


Files produced by the author(s)



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⟩



Record views


Files downloads