On reversible automata

Jean-Éric Pin



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.

PostScript gzipped file, PDF file

Valid HTML 4.01!