Skip to Main content Skip to Navigation
Conference papers

Fast Synchronization of Random Automata

Abstract : A synchronizing word for an automaton is a word that brings that automaton into one and the same state, regardless of the starting position. Černý conjectured in 1964 that if a n-state deterministic automaton has a synchronizing word, then it has a synchronizing word of length at most (n − 1)². Berlinkov recently made a breakthrough in the probabilistic analysis of synchronization: he proved that, for the uniform distribution on deterministic automata with n states, an automaton admits a synchronizing word with high probability. In this article, we are interested in the typical length of the smallest synchronizing word, when such a word exists: we prove that a random automaton admits a synchronizing word of length O(n log3 n) with high probability. As a consequence, this proves that most automata satisfy the Černý conjecture.
Complete list of metadata

Cited literature [18 references]  Display  Hide  Download
Contributor : Admin Upem Connect in order to contact the contributor
Submitted on : Wednesday, February 28, 2018 - 7:34:24 AM
Last modification on : Saturday, January 15, 2022 - 3:56:42 AM
Long-term archiving on: : Monday, May 28, 2018 - 9:56:24 AM


Publisher files allowed on an open archive




Cyril Nicaud. Fast Synchronization of Random Automata. APPROX/RANDOM 2016, Sep 2016, Paris, France. pp.43.1-12, ⟨10.4230/LIPIcs.APPROX-RANDOM.2016.43⟩. ⟨hal-01719171⟩



Record views


Files downloads