2021/05/19 by A. N. Trahtman, Trahtman, A. N. · 2 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · #68915 05C12 #Cellular Automata and Applications #Chemical Synthesis and Analysis #DNA and Biological Computing #F.2.2 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #I.2.7 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2105.09105
openalex publication_date 2021/05/19 · openalex created_date 2025/10/27 · openalex updated_date 2026/07/28
A word w is called a synchronizing (recurrent, reset) word of a deterministic\nfinite automaton (DFA) if w brings all states of the automaton to some state; a\nDFA that has a synchronizing word is said to be synchronizing. Cerny\nconjectured in 1964 that every n-state synchronizing DFA possesses a\nsynchronizing word of length at most (n -1)2. We consider automaton with\naperiodic transition monoid (such automaton is called aperiodic). We show that\nevery synchronizing n-state aperiodic automaton has a synchronizing word of\nlength at most n(n-2)+1. Thus, for aperiodic automaton as well as for\nautomatons accepting only star-free languages, the Cerny conjecture holds true.\n