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 metadatas

Cited literature [18 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-01719171
Contributor : Admin Upem <>
Submitted on : Wednesday, February 28, 2018 - 7:34:24 AM
Last modification on : Thursday, July 5, 2018 - 2:45:48 PM
Long-term archiving on : Monday, May 28, 2018 - 9:56:24 AM

File

random16.pdf
Publisher files allowed on an open archive

Identifiers

Citation

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⟩

Share

Metrics

Record views

66

Files downloads

44