Discrete Mathematics & Theoretical Computer Science, Vol 12, No 4 (2010)

Font Size:  Small  Medium  Large

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