2011/04/26 by Evgeny Skvortsov, Skvortsov, Evgeny, Evgeny Tipikin +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1105.1704
openalex publication_date 2011/04/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we describe an approach to finding the shortest reset word of a finite synchronizing automaton by using a SAT solver. We use this approach to perform an experimental study of the length of the shortest reset word of a finite synchronizing automaton. The largest automata we considered had 100 states. The results of the experiments allow us to formulate a hypothesis that the length of the shortest reset word of a random finite automaton with n states and 2 input letters with high probability is sublinear with respect to n and can be estimated as 1.95 n0.55.