Skip to Main content Skip to Navigation
Journal articles

Synchronizing random automata

Abstract : Conjecture that any synchronizing automaton with n states has a reset word of length (n - 1)(2) was made by. Cerny in 1964. Notwithstanding the numerous attempts made by various researchers this conjecture hasn't been definitively proven yet. 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) > 18 ln n any random automaton is synchronizing with high probability. For m(n) > n(beta), beta > 1/2 we also show that any random automaton with high probability satisfies the. Cerny conjecture.
Document type :
Journal articles
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s Connect in order to contact the contributor
Submitted on : Tuesday, May 13, 2014 - 3:37:29 PM
Last modification on : Wednesday, November 29, 2017 - 10:26:24 AM
Long-term archiving on: : Monday, April 10, 2017 - 10:06:15 PM


Files produced by the author(s)




Evgeny Skvortsov, Yulia Zaks. Synchronizing random automata. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2010, Vol. 12 no. 4 (4), pp.95-108. ⟨10.46298/dmtcs.514⟩. ⟨hal-00990454⟩



Record views


Files downloads