On randomized generation of slowly synchronizing automata

Abstract

Motivated by the randomized generation of slowly synchronizing automata, we study automata made of permutation letters and a merging letter of rank $n-1$. We present a constructive randomized procedure to generate synchronizing automata of that kind with (potentially) large alphabet size based on recent results on \textit{primitive} sets of matrices. We report numerical results showing that our algorithm finds automata with much larger reset threshold than a mere uniform random generation and we present new families of automata with reset threshold of $\Omega (n^2/4)$. We finally report theoretical results on randomized generation of primitive sets of matrices: a set of permutation matrices with a $0$ entry changed into a $1$ is primitive and has exponent of $O(n\log n)$ with high probability in case of uniform random distribution and the same holds for a random set of binary matrices where each entry is set, independently, equal to $1$ with probability $p$ and equal to $0$ with probability $1-p$, when $np-\log n\to \infty$ as $n\to \infty$.

21 pages, 8 figures. Revised argument for Theorem 18, minor changes in Section 3. To appear in the Proceedings of MFCS 2018