An improvement to a recent upper bound for synchronizing words of finite automata

Abstract

It has been known since the 60's that any complete discrete $n$-state automaton admits a reset word of length not exceeding $\alpha n^3+o(n^3)$ for some absolute constant $\alpha$. J.-E. Pin and P. Frankl proved this statement with $\alpha =1/6=\mathrm{0.1666...}$ in 1982, and this bound remained best known until 2017, when M. Szykuła decreased its value to $\alpha \approx 0.1664$. In this note, we present a modification to the latest approach and develop a different counting argument which leads to a more substantial improvement of $\alpha ⩽0.1654$.

5 pages