2026-07-27T03:57:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6666 2024-03-06T10:38:38Z ddc:004 open_access

Fast Synchronization of Random Automata Nicaud, Cyril random automata synchronization the Černý conjecture A synchronizing word for an automaton is a word that brings that automaton into one and the same state, regardless of the starting position. Cerny 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)^2. 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 log^{3}n) with high probability. As a consequence, this proves that most automata satisfy the Cerny conjecture. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Cyril Nicaud 2016 Is Part Of LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2016.43 urn:nbn:de:0030-drops-66665 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.43 eng https://creativecommons.org/licenses/by/3.0/legalcode