Abstract:
We exhibit several infinite series of synchronizing automata. The minimum length of reset words for each of the automata is close to the state number squared. All these automata are tightly related to primitive directed graphs with large exponents.
Key words and phrases:primitive digraph, exponent of a digraph, synchronizing automaton, reset word, synchronization threshold, coloring of a digraph.
Fulltext:
PDF file (368 kB)