Complexity of Road Coloring with Prescribed Reset Words

Abstrakt

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.

Klíčová slova

• Algorithms on automata and words
• Road coloring theorem
• Road coloring problem
• Reset word
• Synchronizing word