Fast Synchronization of Random Automata - Archive ouverte HAL Accéder directement au contenu
Communication Dans Un Congrès Année : 2016

Fast Synchronization of Random Automata

Cyril Nicaud

Résumé

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.
Fichier principal
Vignette du fichier
random16.pdf (566.49 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-01719171 , version 1 (28-02-2018)

Identifiants

Citer

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⟩
56 Consultations
55 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More