2022/06/10 by Balázs Gerencsér, Gerencsér, Balázs, Zsombor Várkonyi +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #68Q45 (Primary) 05A05 #68R05 (Secondary) #Algorithms and Data Compression #Combinatorics (math.CO) #DNA and Biological Computing #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2206.05043
openalex publication_date 2022/06/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We examine the reset threshold of randomly generated deterministic automata. We present a simple proof that an automaton with a random mapping and two random permutation letters has a reset threshold of O( √(n log3 n) ) with high probability, assuming only certain partial independence of the letters. Our observation is motivated by Nicaud (2014) providing a near-linear bound in the case of two random mapping letters, among multiple other results. The upper bound for the latter case has been recently improved by the breakthrough work of Chapuy and Perarnau (2023) to O(√(n) log n).