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.
Type de document :
Communication dans un congrès
Cezar Câmpeanu; Florin Manea; Jeffrey Shallit. 18th International Workshop on Descriptional Complexity of Formal Systems (DCFS), Jul 2016, Bucharest, Romania. Springer International Publishing, Lecture Notes in Computer Science, LNCS-9777, pp.168-179, 2016, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-41114-9_13〉
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01633945
Contributeur : Hal Ifip <>
Soumis le : lundi 13 novembre 2017 - 15:32:21
Dernière modification le : lundi 13 novembre 2017 - 15:35:37
Document(s) archivé(s) le : mercredi 14 février 2018 - 15:22:15

Fichier

 Accès restreint
Fichier visible le : 2019-01-01

Connectez-vous pour demander l'accès au fichier

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Giovanna Lavado, Giovanni Pighizzini, Luca Prigioniero. Minimal and Reduced Reversible Automata. Cezar Câmpeanu; Florin Manea; Jeffrey Shallit. 18th International Workshop on Descriptional Complexity of Formal Systems (DCFS), Jul 2016, Bucharest, Romania. Springer International Publishing, Lecture Notes in Computer Science, LNCS-9777, pp.168-179, 2016, Descriptional Complexity of Formal Systems. 〈10.1007/978-3-319-41114-9_13〉. 〈hal-01633945〉

Partager

Métriques

Consultations de la notice

34