Recently, a series of papers have started to look at Cerný‘s conjecture, and in general at synchronizing automata, from the point of view of the theory of ideals of free monoids. The starting point of such an approach is a simple observation: the set of reset words of an automaton is a two-sided ideal of the free monoid on its alphabet that is also a regular language. We study the relationship between a synchronizing automaton and the sets of (minimal) generators of its reset words. We show that if such set does not contain a word of a certain length, then Cerný‘s conjecture holds.
Missing factors of ideals and synchronizing automata
Frigeri A.;Rodaro E.
2019-01-01
Abstract
Recently, a series of papers have started to look at Cerný‘s conjecture, and in general at synchronizing automata, from the point of view of the theory of ideals of free monoids. The starting point of such an approach is a simple observation: the set of reset words of an automaton is a two-sided ideal of the free monoid on its alphabet that is also a regular language. We study the relationship between a synchronizing automaton and the sets of (minimal) generators of its reset words. We show that if such set does not contain a word of a certain length, then Cerný‘s conjecture holds.File in questo prodotto:
File | Dimensione | Formato | |
---|---|---|---|
Missing factors of ideals.pdf
Accesso riservato
:
Publisher’s version
Dimensione
518.95 kB
Formato
Adobe PDF
|
518.95 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.