Length of a synchronizing word of finite automata
Question
What is the maximal length of a shortest synchronizing word over an automaton.
Known results
Lower bound is asymptotically $n^2$.
Upper bound is asymptotically $n^3$. Consider the shortest synchronizing word W for an automata.
- A Note on Homogeneous Experiments with Finite Automata, 1964 ↗
- Pin 1983 ${n^3-n \over 6}$ upper bound
- $n^2$ was shown for few classes of synchronizing automata
- On two combinatorial problems arising from automatatheory, 1981 ↗
- Kari 2003, if the underlying digraph is Eulerian, then the minimum reset word is of length at most (n-2)(n-1)+1 (open of tight?)
- Trahtman 2011 ${7n^3+12n^2-4n \over 48}$
Videos
- Around the Cerny conjecture ↗
- An overview of the Černý Conjecture part 1 ↗
- An overview of the Černý Conjecture part 2 ↗ – wrong cubic upper bound mentioned in the middle