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 characterization relates
reversible automata to the profinite group topology of the free monoid.
PostScript
gzipped file, PDF file