A Lower Bound For Reversible Automata
Pierre‐Cyrille Héam · 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 Kn on A which can be accepted by a reversible automaton, and such that the number of states of the minimal automaton of Kn is in O(n), while the minimal number of states of a reversible automaton accepting Kn is in O(ρn) for some ρ > 1? We give such an example with .