论文标题
快速同步非稳态随机自动机
Fast synchronization of inhomogenous random automata
论文作者
论文摘要
我们检查随机生成的确定性自动机的重置阈值。我们提供了一个简单的证据，表明具有随机映射和两个随机排列字母的自动机具有$ \ Mathcal {o} \ big（\ sqrt {n \ log^3 n} \ big）$的重置阈值，具有很高的可能性，假设字母的某些部分独立性。 Nicaud（2014）激发了我们的观察结果，在两个随机映射字母的情况下，在其他多个结果中提供了几乎线性的界限。最近，Chapuy和Perarnau（2023）的突破性作品（2023）到$ \ Mathcal {o}（\ sqrt {n} \ log n）$最近，对后一种情况的上限得到了改善。
We examine the reset threshold of randomly generated deterministic automata. We present a simple proof that an automaton with a random mapping and two random permutation letters has a reset threshold of $\mathcal{O}\big( \sqrt{n \log^3 n} \big)$ with high probability, assuming only certain partial independence of the letters. Our observation is motivated by Nicaud (2014) providing a near-linear bound in the case of two random mapping letters, among multiple other results. The upper bound for the latter case has been recently improved by the breakthrough work of Chapuy and Perarnau (2023) to $\mathcal{O}(\sqrt{n} \log n)$.
