论文标题
随机自动机的简短同步单词
Short Synchronizing Words for Random Automata
论文作者
论文摘要
我们证明，在2个字母的字母上，具有$ n $状态的均匀随机自动机具有一个长度$ o（n^{1/2} \ log n）$的同步单词，具有高概率（W.H.P.）。也就是说，W.H.P.存在此类长度的单词$ω$和一个状态$ v_0 $，因此$ω$将所有状态发送到$ v_0 $。在这项工作之前，最佳上限是由于nicaud（2016）而导致的quasilinear绑定$ o（n \ log^3n）$。基于数值模拟，正确的缩放指数已受其他作者的估计，在$ 0.5 $和0.56 $之间，我们的结果证实，最小的结果确实给出了有效的上限（带有日志因子）。 我们的证明介绍了$ w $树的概念，对于单词$ w $，即$ w $ transitions诱导一棵（循环根）树的自动机。我们证明了一个强大的结构结果，它说，W.H.P.，$ n $状态上的随机自动机是$ w $ -tree，对于某个单词$ w $，最多$ w $（1+ε）\ log_2（n）$，对于任何$ε> 0 $。概率方法证明了（随机）单词$ w $的存在。这种结构结果是证明存在简短同步单词的关键。
We prove that a uniformly random automaton with $n$ states on a 2-letter alphabet has a synchronizing word of length $O(n^{1/2}\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 $v_0$, such that $ω$ sends all states to $v_0$. Prior to this work, the best upper bound was the quasilinear bound $O(n\log^3n)$ due to Nicaud (2016). The correct scaling exponent had been subject to various estimates by other authors between $0.5$ and $0.56$ based on numerical simulations, and our result confirms that the smallest one indeed gives a valid upper bound (with a log factor). 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+ε)\log_2(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.
