2014/12/02 by Vojtěch Vorel, Vorel, Vojtěch, Adam Roman +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced Graph Theory Research #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.1412.0799
openalex publication_date 2014/12/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
By the Road Coloring Theorem (Trahtman, 2008), the edges of any aperiodic directed multigraph with a constant out-degree can be colored such that the resulting automaton admits a reset word. There may also be a need for a particular reset word to be admitted. For certain words it is NP-complete to decide whether there is a suitable coloring of a given multigraph. We present a classification of all words over the binary alphabet that separates such words from those that make the problem solvable in polynomial time. We show that the classification becomes different if we consider only strongly connected multigraphs. In this restricted setting the classification remains incomplete.