2018/01/01 by de Bondt, M., de Bondt, Michiel, Don, H.M. +3 · 1 citation
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.1801.10436
openalex publication_date 2018/01/01 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/14
It was conjectured by Černý in 1964, that a synchronizing DFA on n states always has a synchronizing word of length at most (n−1) 2 , and he gave a sequence of DFAs for which this bound is reached. Until now a full analysis of all DFAs reaching this bound was only given for n≤5 , and with bounds on the number of symbols for n≤12 . Here we give the full analysis for n≤7 , without bounds on the number of symbols. <br/>For PFAs (partial automata) on ≤7 states we do a similar analysis as for DFAs and find the maximal shortest synchronizing word lengths, exceeding (n−1) 2 for n≥4 . Where DFAs with long synchronization typically have very few symbols, for PFAs we observe that more symbols may increase the synchronizing word length. For PFAs on ≤10 states and two symbols we investigate all occurring synchronizing word lengths. <br/>We give series of PFAs on two and three symbols, reaching the maximal possible length for some small values of n . For n=6,7,8,9 , the construction on two symbols is the unique one reaching the maximal length. For both series the growth is faster than (n−1) 2 , although still quadratic. <br/>Based on string rewriting, for arbitrary size we construct a PFA on three symbols with exponential shortest synchronizing word length, giving significantly better bounds than earlier exponential constructions. We give a transformation of this PFA to a PFA on two symbols keeping exponential shortest synchronizing word length, yielding a better bound than applying a similar known transformation. Both PFAs are transitive. <br/>Finally, we show that exponential lengths are even possible with just one single undefined transition, again with transitive constructions.