Short Synchronizing Words for Random Automata

Abstract

We prove that a uniformly random automaton with n states on a 2-letter alphabet has a synchronizing word of length O(√n log n) with high probability (w.h.p.). That is to say, w.h.p. there exists a word ω of such length, and a state v0, such that ω sends all states to v0. This confirms a conjecture of Kisielewicz, Kowalski, Szykuła [KKS13] based on numerical simulations, up to a log factor - the previous best partial result towards the conjecture was the quasilinear bound O(nlog3 n) due to Nicaud [Nic19]. Moreover, the synchronizing word ω we obtain has small entropy, in the sense that it can be encoded with only O(log(n)) bits w.h.p.. Our proof introduces the concept of w-trees, for a word w, that is, automata in which the w-transitions induce a (loop-rooted) tree. We prove a strong structure result that says that, w.h.p., a random automaton on n states is a w-tree for some word w of length at most (1 + ε) log2(n), for any ε > 0. The existence of the (random) word w is proved by the probabilistic method. This structure result is key to proving that a short synchronizing word exists. Copyright © 2023 by SIAM.