Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadatas

https://hal-upec-upem.archives-ouvertes.fr/hal-00620037
Contributor : Sylvain Lombardy <>
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

File

hal.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00620037, version 1

Citation

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⟩

Share

Metrics

Record views

172

Files downloads

184