A Quadratic Upper Bound on the Reset Thresholds of Synchronizing Automata Containing a Transitive Permutation Group
Yinfeng Zhu · arXiv (Cornell University) · 2024
For any synchronizing $n$-state deterministic automaton, Černý conjectures the existence of a synchronizing word of length at most $(n-1)^2$. We prove that there exists a synchronizing word of length at most $2n^2 - 7n + 7$ for every synchronizing $n$-state deterministic automaton that satisfies the following two properties: 1. The image of the action of each letter contains at least $n-1$ states; 2. The actions of bijective letters generate a transitive permutation group on the state set.