A Lower Bound For Reversible Automata
Héam, Pierre-Cyrille; Héam Pierre-Cyrille; LIAFA, Université Paris 7, 2 place Jussieu, 75251 Paris Cedex 05, France; (heam@liafa.jussieu.fr)
Журнал:
RAIRO - Theoretical Informatics and Applications
Дата:
2000
Аннотация:
A reversible automaton is a finite automaton in which each letter induces a partial one-to-one map from the set of states into itself. We solve the following problem proposed by Pin. Given an alphabet A, does there exist a sequence of languages K <sub> n </sub> on A which can be accepted by a reversible automaton, and such that the number of states of the minimal automaton of K <sub> n </sub> is in O(n), while the minimal number of states of a reversible automaton accepting K <sub> n </sub> is in O(ρ <sup> n </sup>) for some ρ > 1? We give such an example with $\rho=\left(\frac{9}{8}\right)^{\frac{1}{12}}$.
157.3Кб