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 (CEUR WORKSHOP PROCEEDINGS). - In: Italian Conference on Theoretical Computer Science / [a cura di] V. Bilò, A. Caruso. - [s.l] : CEUR-WS, 2016 Dec 06. - pp. 234-239 (( Intervento presentato al 17. convegno ICTCS tenutosi a Lecce nel 2016.

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.
Settore INF/01 - Informatica
6-dic-2016
Department of Mathematics and Physics "Ennio De Giorgi"
Fondazione Puglia
Italian Chapter of the European Association of Theoretical Computer Science (EATCS)
Università del Salento
http://ceur-ws.org/Vol-1720/
Book Part (author)
File in questo prodotto:
File Dimensione Formato  
short3.pdf

accesso aperto

Tipologia: Publisher's version/PDF
Dimensione 302.21 kB
Formato Adobe PDF
302.21 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/471398
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
  • OpenAlex ND
social impact