Combinatorics Seminar
When: Sunday, November 4, 10am
Where: Schreiber 309
Speaker: Avraham Trakhtman, Bar Ilan University
Title: The road coloring problem
Abstract:
A synchronizing word of a deterministic automaton is a word in the
alphabet of colors (considered as letters) on 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 originated in 1970 and was stated explicitly in
1977 by Adler, Goodwyn and Weiss for a strongly connected directed finite
graph with constant outdegree of all its vertices where the greatest
common divisor of lengths of all its cycles is one. The edges of the
graph are unlabeled.The road coloring problem is connected with the
problem of existence of synchronizing word for deterministic complete
finite automaton.
The problem is important in automata theory: a synchronizing coloring
makes the behavior of an automaton resistant against input errors since,
after detection of an error, a synchronizing word can reset the automaton
back to its original state, as if no error had occurred.
The problem appeared first in the context of symbolic dynamics. It evoked
noticeable interest among the specialists in the theory of graphs,
automata and symbolic dynamics and is discussed even in "Wikipedia",
the popular Internet Encyclopedia. Together with the Cerny conjecture,
the road coloring problem belongs to the most fascinating mathematical
problems in the theory of finite automata.
We present a solution of the road coloring problem.