On the construction of reversible automata for reversible languages

Sylvain Lombardy (1)

1 LTCI - Laboratoire Traitement et Communication de l'Information

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.

Domaines: Algorithme et structure de données [cs.DS]

Sylvain Lombardy. On the construction of reversible automata for reversible languages. 29th International Colloquium on Automata, Languages and Programming (ICALP 2002), Jul 2002, Malaga, Spain, Spain. pp.170-182. ⟨hal-00620037⟩