Abstract:
Using the combinatorial properties of uncovering sets in a free monoid, we construct a series of finite deterministic synchronizing automata with zero for which the shortest synchronizing word has length $n^2/4+n/2-1$, where $n$ is the number of states.
Keywords:
free monoid, uncovering set, deterministic and nondeterministic automaton, synchronizing automaton (with zero), synchronizing word, maximal code.
Citation:
E. V. Pribavkina, “Slowly Synchronizing Automata with Zero and Uncovering Sets”, Mat. Zametki, 90:3 (2011), 422–430; Math. Notes, 90:3 (2011), 411–417