SUNGBIN HONG

cs.FL — Formal Languages and Automata Theory

Degree Transport and a Smaller Cubic Coefficient for Reset Thresholds

Contributed by SUNGBIN HONG

We prove that every synchronizing complete deterministic finite automaton on $n\ge2$ states has reset threshold at most $\frac{8242}{49923}n^3+O(n^2)$. The cubic coefficient improves on Shitov's $8257/49923$ by $5/16641$. The main ingredient is a degree-transport inequality for graphs of state pairs mergeable by short words. It relates a long gap between consecutive minimum-rank word lengths to a large corank achievable in at most $n-1$ letters. Combining this relation with a discrete dual of Shitov's counting argument gives the improvement. An appendix makes the quadratic remainder explicit for every $n\ge2$. The argument applies to arbitrary finite alphabets and does not prove the quadratic Černý conjecture.