On the probability of being synchronizable

Abstract

We prove that a random binary automaton with $n$ states is synchronizing with high probability and the asymptotic is exactly $1-\Theta (\frac{1}{n})$ as conjectured in [Cameron, 2011]. We also present a deterministic algorithm which decides whether a given random automaton is synchronizing in expected time linear in $n$ and prove that it is optimal. This is an expanded and heavily revised version of the conference paper [Berlinkov, 2016] with an addition of the algorithmic result described above.

Major revision

Cited by in corpus (3)

• Highest Trees of Random Mappings
• Testing for Synchronization
• Synchronizing automata with random inputs