This paper mainly concerns the property of strong local transitivity of finite automata. We will survey some results on this property in the context of the synchronization problem. Further aspects and results relating this problem with the Road coloring problem of finite oriented graphs and the Restivo conjecture on the minimal length of an incompletable word of a finite language of words, are also analyzed.
Locally strongly transitive automata in the Cerny conjecture and related problems / Carpi, Arturo; D'Alessandro, Flavio. - In: JOURNAL OF AUTOMATA, LANGUAGES AND COMBINATORICS. - ISSN 1430-189X. - 24:2--4(2019), pp. 165-184.
Locally strongly transitive automata in the Cerny conjecture and related problems
D'Alessandro Flavio
2019
Abstract
This paper mainly concerns the property of strong local transitivity of finite automata. We will survey some results on this property in the context of the synchronization problem. Further aspects and results relating this problem with the Road coloring problem of finite oriented graphs and the Restivo conjecture on the minimal length of an incompletable word of a finite language of words, are also analyzed.| File | Dimensione | Formato | |
|---|---|---|---|
|
Carpi_Locally-strongly_2019.pdf
solo gestori archivio
Tipologia:
Documento in Post-print (versione successiva alla peer review e accettata per la pubblicazione)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
668.19 kB
Formato
Adobe PDF
|
668.19 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
