An improvement to a recent upper bound for synchronizing words of finite automata

2019/01/19 by Shitov, Yaroslav · 2 citations
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1901.06542

Abstract

It has been known since the 60's that any complete discrete n-state automaton admits a reset word of length not exceeding αn³+o(n³) for some absolute constant α. J.-E. Pin and P. Frankl proved this statement with α=1/6=0.1666... in 1982, and this bound remained best known until 2017, when M. Szykuła decreased its value to α≈0.1664. In this note, we present a modification to the latest approach and develop a different counting argument which leads to a more substantial improvement of α\leqslant 0.1654.

Cited by

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

Related

• Modifying the upper bound on the length of minimal synchronizing word
• List of Results on the Černý Conjecture and Reset Thresholds for Synchronizing Automata
• Experimental Study of the Shortest Reset Word of Random Automata
• Algebraic synchronization criterion and computing reset words
• Generating Synchronizing Automata with Large Reset Lengths