%0 Conference Proceedings
%T Minimal and Reduced Reversible Automata
%+ Università degli Studi di Milano = University of Milan (UNIMI)
%A Lavado, Giovanna, J.
%A Pighizzini, Giovanni
%A Prigioniero, Luca
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 18th International Workshop on Descriptional Complexity of Formal Systems (DCFS)
%C Bucharest, Romania
%Y Cezar Câmpeanu
%Y Florin Manea
%Y Jeffrey Shallit
%I Springer International Publishing
%3 Descriptional Complexity of Formal Systems
%V LNCS-9777
%P 168-179
%8 2016-07-05
%D 2016
%R 10.1007/978-3-319-41114-9_13
%Z Computer Science [cs]Conference papers
%X 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.
%G English
%Z TC 1
%Z WG 1.2
%2 https://inria.hal.science/hal-01633945/document
%2 https://inria.hal.science/hal-01633945/file/416473_1_En_13_Chapter.pdf
%L hal-01633945
%U https://inria.hal.science/hal-01633945
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-WG
%~ IFIP-DCFS
%~ IFIP-LNCS-9777
%~ IFIP-WG1-2