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.
Minimal and reduced reversible automata / G.J. Lavado, G. Pighizzini, L. Prigioniero (LECTURE NOTES IN COMPUTER SCIENCE). - In: Descriptional Complexity of Formal Systems / [a cura di] C. Câmpeanu, F. Manea, J. Shallit. - [s.l] : Springer, 2016. - ISBN 9783319411132. - pp. 168-179 (( Intervento presentato al 18. convegno DCFS tenutosi a Bucharest nel 2016 [10.1007/978-3-319-41114-9_13].
Minimal and reduced reversible automata
G.J. Lavado;G. Pighizzini;L. Prigioniero
2016
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.File | Dimensione | Formato | |
---|---|---|---|
reversibleDCFSfinal.pdf
accesso aperto
Tipologia:
Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione
280.46 kB
Formato
Adobe PDF
|
280.46 kB | Adobe PDF | Visualizza/Apri |
chp%3A10.1007%2F978-3-319-41114-9_13.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
269.1 kB
Formato
Adobe PDF
|
269.1 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.