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.
Fulltext:
PDF file (512 kB)
