The quadratic upper bound of the Černý Conjecture
Qinghe Pan · HAL (Le Centre pour la Communication Scientifique Directe) · 2026
The Černý conjecture is a long-standing open problem in the theory of finite synchronizing automata. In this paper we introduce a new intuitive approach to establish an upper bound on reset thresholds for Černý synchronizing automata with n states and alphabet {a, b}. The method avoids heavy combinatorial constructions used in many previous works and focued on the properties of the shortest reset word w s . By analyzing the properties of w s in powerset automata some intrinsic relations between w s and state sets are identified. We prove that the length of w s in Černý and other strongly connected synchronizing automata is O(n 2 ).