### Synchronizing random automata

*Evgeny Skvortsov, Yulia Zaks*

#### Abstract

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