Résumé :
Un automate
réversible est un automate fini (éventuellement incomplet)
dans lequel l'action de chaque lettre définit une fonction injective
de l'ensemble des états dans lui-même. Nous donnons quatre
caractérisations des langages acceptés par un automate
réversible muni d'un ensemble d'états initiaux et d'un
ensemble d'états finaux. Nous montrons que l'on peut décider
de manière effective si un langage rationnel donné peut
être accepté par un automate réversible. La
première caractérisation donne une description des parties du
groupe libre reconnues par un automate réversible qui n'est pas sans
rappeler le théorème de Kleene. La seconde
caractérisation est de nature plus combinatoire. La
décidabilité résulte de la troisième
caractérisation, de nature algébrique. La dernière
caractérisation relie les automates réversibles et la
topologie pro-groupe du monoïde libre.
Abstract : A reversible automaton is a finite
(possibly incomplete) automaton in which each letter induces a partial
one-to-one map from the set of states into itself. We give four
non-trivial characterizations of the languages accepted by a reversible
automaton equipped with a set of initial and final states and we show that
one can effectively decide whether a given rational (or regular) language
can be accepted by a reversible automaton. The first characterization
gives a description of the subsets of the free group accepted by a
reversible automaton that is somewhat reminiscent of Kleene's theorem. The
second characterization is more combinatorial in nature. The decidability
follows from the third -- algebraic -- characterization. The last and
somewhat unexpected characterization is a topological description of our
languages that solves an open problem about the finite-group topology of
the free monoid.