Article contents
A Lower Bound For Reversible Automata
Published online by Cambridge University Press: 15 April 2002
Abstract
A reversible automaton is a finite automaton in which eachletter induces a partial one-to-one map from the set of states intoitself. We solve the following problem proposed by Pin. Given an alphabet A, does there exist a sequence of languages K n on A which can be accepted by a reversible automaton, and such that the number of states of the minimal automaton of K n is in O(n), while the minimal number of states of a reversible automaton accepting K n is in O(ρ n ) for some ρ > 1? We give such an example with $\rho=\left(\frac{9}{8}\right)^{\frac{1}{12}}$ .
- Type
- Research Article
- Information
- RAIRO - Theoretical Informatics and Applications , Volume 34 , Issue 5 , September 2000 , pp. 331 - 341
- Copyright
- © EDP Sciences, 2000
References
- 7
- Cited by