Paper Info
Title
The road coloring problem
Abstract
A synchronizing word of a deterministic automaton is a word in the alphabet of colors (considered as letters) of its edges that maps the au- tomaton 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.
Year
DOI
Venue
2007
10.1007/s11856-009-0062-5
Israel Journal of Mathematics
Keywords
DocType
Volume
syn- chronization.,graph,road coloring problem,deterministic finite automaton,greatest common divisor,connected graph,directed graph,symbolic dynamics
Journal
172
Issue
ISSN
Citations 
1
1565-8511
13
PageRank 
References 
Authors
1.08
4
1
Name
Order
Citations
PageRank
A. N. Trahtman19211.68