Publication at Faculty of Mathematics and Physics |
2015
Abstract
By the Road Coloring Theorem (Trahtman, 2008), the edges of any given 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. For the binary alphabet, we present a classification that separates such words from those that make the problem solvable in polynomial time.
The classi- fication differs if we consider only strongly connected multigraphs. In this restricted setting the classification remains incomplete.