On the construction of reversible automata for reversible languages

Abstract : Reversible languages occur in many different domains. Although the decision for the membership of reversible languages was solved in 1992 by Pin, an effective construction of a reversible automaton for a reversible language was still unknown. We give in this paper a method to compute a reversible automaton from the minimal automaton of a reversible language. With this intention, we use the universal automaton of the language that can be obtained from the minimal automaton and that contains an equivalent automaton which is quasi-reversible. This quasi-reversible automaton has nearly the same properties as a reversible one and can easily be turnes into a reversible automaton.