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.
https://hal-upec-upem.archives-ouvertes.fr/hal-00620037 Contributor : Sylvain LombardyConnect in order to contact the contributor Submitted on : Monday, October 3, 2011 - 3:34:16 PM Last modification on : Friday, July 31, 2020 - 10:44:05 AM Long-term archiving on: : Wednesday, January 4, 2012 - 2:26:09 AM
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⟩