2013/04/21 by Mikhail V. Berlinkov, Berlinkov, Mikhail V. · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Combinatorics (math.CO) #DNA and Biological Computing #Discrete Mathematics (cs.DM) #F.4.3 #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1304.5774
openalex publication_date 2013/04/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We prove that a random automaton with n states and any fixed non-singleton alphabet is synchronizing with high probability (modulo an unpublished result about unique highest trees of random graphs). Moreover, we also prove that the convergence rate is exactly 1-Θ((1)/(n)) as conjectured by [Cameron, 2011] for the most interesting binary alphabet case. Finally, we present a deterministic algorithm which decides whether a given random automaton is synchronizing in linear in n expected time and prove that it is optimal.