Short Synchronizing Words for Random Automata

DOI10.1137/1.9781611977554.CH26arXiv2207.14108OpenAlexW4316652393MaRDI QIDQ6406364FDOQ6406364

Authors: Guillaume Chapuy, Guillem Perarnau 

Publication date: 28 July 2022

Abstract: 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}logn)$ with high probability (w.h.p.). That is to say, w.h.p. there exists a word $omega$ of such length, and a state $v_0$, such that $omega$ sends all states to $v_0$. Prior to this work, the best upper bound was the quasilinear bound $O(nlo{g}^{3}n)$ 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+epsilon)lo{g}_2(n)$, for any $epsilon>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.

Full work available at URL: https://doi.org/10.1137/1.9781611977554.ch26

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cited In (1)

• A Telescopic Proof of Cayley’s Formula

This page was built for publication: Short Synchronizing Words for Random Automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6406364)