A quadratic upper bound on the reset thresholds of synchronizing automata containing a transitive permutation group
<|reference_start|>A quadratic upper bound on the reset thresholds of synchronizing automata containing a transitive permutation group: For any synchronizing $n$-state deterministic automaton, \v{C}ern\'{y} 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.<|reference_end|>
@article{zhu2024a,
    title={A quadratic upper bound on the reset thresholds of synchronizing
  automata containing a transitive permutation group},
    author={Yinfeng Zhu},
    journal={arXiv preprint arXiv:2407.08135},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.08135},
    primaryClass={cs.FL}
}