A quadratic upper bound on the reset thresholds of synchronizing automata containing a transitive permutation group

2024/07/11 by Zhu, Yinfeng · 1 citation
#68Q45 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)

paper · doi:10.48550/arxiv.2407.08135

Abstract

For any synchronizing n-state deterministic automaton, Černý conjectures the existence of a synchronizing word of length at most (n-1)². We prove that there exists a synchronizing word of length at most 2n² - 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.

Cited by

• List of Results on the Černý Conjecture and Reset Thresholds for Synchronizing Automata

Related

• Synchronizing Automata on Quasi Eulerian Digraph
• The vCerny Conjecture for aperiodic automata
• Modifying the upper bound on the length of minimal synchronizing word
• Fast Synchronization of Random Automata
• List of Results on the Černý Conjecture and Reset Thresholds for Synchronizing Automata