Minimal and Reduced Reversible Automata

Abstract : A condition characterizing the class of regular languages which have several nonisomorphic minimal reversible automata is presented. The condition concerns the structure of the minimum automaton accepting the language under consideration. It is also observed that there exist reduced reversible automata which are not minimal, in the sense that all the automata obtained by merging some of their equivalent states are irreversible. Furthermore, it is proved that if the minimum deterministic automaton accepting a reversible language contains a loop in the “irreversible part” then it is always possible to construct infinitely many reduced reversible automata accepting such a language.
Document type :
Conference papers
Liste complète des métadonnées

Cited literature [11 references]  Display  Hide  Download

https://hal.inria.fr/hal-01633945
Contributor : Hal Ifip <>
Submitted on : Monday, November 13, 2017 - 3:32:21 PM
Last modification on : Monday, November 13, 2017 - 3:35:37 PM
Document(s) archivé(s) le : Wednesday, February 14, 2018 - 3:22:15 PM

File

416473_1_En_13_Chapter.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Giovanna Lavado, Giovanni Pighizzini, Luca Prigioniero. Minimal and Reduced Reversible Automata. 18th International Workshop on Descriptional Complexity of Formal Systems (DCFS), Jul 2016, Bucharest, Romania. pp.168-179, ⟨10.1007/978-3-319-41114-9_13⟩. ⟨hal-01633945⟩

Share

Metrics

Record views

40

Files downloads

8