|
A synchronizing word of a deterministic automaton is a word in
the alphabet of colors (considered as letters) of its edges that
maps the automaton to a single state. A coloring of edges of a
directed graph is synchronizing if the coloring turns the graph
into a deterministic finite automaton possessing a synchronizing word.
The road coloring problem is the problem of synchronizing coloring
of a directed finite strongly connected graph with constant outdegree
of all its vertices if the greatest common divisor of lengths
of all its cycles is one. The problem was posed by Adler, Goodwyn
and Weiss over 30 years ago and evoked noticeable interest among
the specialists in the theory of graphs, deterministic automata
and symbolic dynamics.
The positive solution of the road coloring problem is presented.
Some consequences on the length of the synchronizing word are discussed.
|
