On the complexity of computing the profinite closure of a rational language |
| |
Authors: | P.-C. Hé am |
| |
Affiliation: | Projet INRIA-CASSIS, Laboratoire d’Informatique de l’Université de Franche-Comté, 16 route de Gray, 25030 Besançon Cedex, France |
| |
Abstract: | Profinite topology is used in the classification of rational languages. 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. |
| |
Keywords: | Finite automata State complexity Profinite topology |
本文献已被 ScienceDirect 等数据库收录! |
|