A Lower Bound For Reversible Automata

LIAFA, Université Paris 7, 2 place Jussieu, 75251 Paris Cedex 05, France; (heam@liafa.jussieu.fr)

Received: 9 February 2000
Accepted: 29 September 2000

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 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(ρⁿ) for some ρ > 1? We give such an example with .

Résumé

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 K_n sur A qui peuvent être reconnus par un automate réversible, et tels que le nombre d'états de l'automate minimal de K_n soit en O(n) alors que le nombre minimal d'états d'un automate réversible reconnaissant K_n soit en O(ρⁿ) avec ρ > 1 ? On donne un tel exemple avec .