A Lower Bound For Reversible Automata

Abstract

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 . Un automate réversible est un automate fini dans lequel chaque lettre réalise une fonction injective de l'ensemble des états dans lui-même. On résout dans cet article le problème suivant posé par Pin : étant donné un alphabet A, existe-t-il une suite de langages Kn sur A qui peuvent être reconnus par un automate réversible, et tels que le nombre d'états de l'automate minimal de Kn soit en O(n) alors que le nombre minimal d'états d'un automate réversible reconnaissant Kn soit en O(ρn) avec ρ > 1 ? On donne un tel exemple avec .