Question

What is the maximal length of a shortest synchronizing word over an automaton.

Known results

Lower bound is asymptotically $n^2$.

Lower bound construction

Upper bound is asymptotically $n^3$. Consider the shortest synchronizing word W for an automata.

Upper bound proof

Videos