Discrete Mathematics & Theoretical Computer Science, Vol 12, No
4 (2010)  Font Size:  Small  Medium  Large  Synchronizing random
automata  Evgeny Skvortsov, Yulia Zaks   Conjecture that any
synchronizing automaton with $n$ states has a reset word of
length $(n-1)^2$ was made by \v{C}ern\'{y} in 1964. Despite
attracting a lot of attention of researches it remains unproven
since then. In this paper we study a random automaton that is
sampled uniformly at random from the set of all automata with
$n$ states and $m(n)$ letters. We show that for $m(n)>36 \ln n$
the random automaton is synchronizing with high probability. For
$m(n)>n^\beta, \beta>1/2$ we also show that the random automaton
with high probability satisfies the \v{C}ern\'{y} conjecture.
Full Text: PDF PostScript