2023/06/15 by Anders Martinsson, Martinsson, Anders
Biochemistry, Genetics and Molecular Biology · Computer Science · #Cellular Automata and Applications #Combinatorics (math.CO) #DNA and Biological Computing #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Probability (math.PR) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2306.09040
openalex publication_date 2023/06/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In a recent article by Chapuy and Perarnau, it was shown that a uniformly chosen automaton on n states with a 2-letter alphabet has a synchronizing word of length O(√(n)log n) with high probability. In this note, we improve this result by showing that, for any ε>0, there exists a synchronizing word of length O(ε-1√(n log n)) with probability 1-ε. Our proof is based on two properties of random automata. First, there are words ω of length O(√(n log n)) such that the expected number of possible states for the automaton, after inputting ω, is O(√(n/log n)). Second, with high probability, each pair of states can be synchronized by a word of length O(log n).