The road coloring problem

by: AN Trahtman

(21 Dec 2007)

View FullText article

arXiv (abstract), arXiv (PDF)

Reviews [Write a review of this article]

There are no reviews of this article

Find related articles from these CiteULike users

elsantosneto, eimaj42jdp

Find related articles with these CiteULike tags

automata, coloring, combinatorics, graph, graphs, mathematical, maths, networks, problem, routing

摘要

The synchronizing word of 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 deterministic finite automaton possessing a synchronizing word. The road coloring problem is a problem of synchronizing coloring of 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 a noticeable interest among the specialists in theory of graphs, deterministic automata and symbolic dynamics. The problem is described even in "Wikipedia" - the popular Internet Encyclopedia. The positive solution of the road coloring problem is presented.

@misc{citeulike:2575181, abstract = {The synchronizing word of 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 deterministic finite automaton possessing a synchronizing word. The road coloring problem is a problem of synchronizing coloring of 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 a noticeable interest among the specialists in theory of graphs, deterministic automata and symbolic dynamics. The problem is described even in "Wikipedia" - the popular Internet Encyclopedia. The positive solution of the road coloring problem is presented.}, author = {Trahtman, A. N. }, citeulike-article-id = {2575181}, eprint = {0709.0099}, keywords = {automata, combinatorics, graph, maths}, month = {Dec}, posted-at = {2008-04-30 15:49:04}, priority = {1}, title = {The road coloring problem}, url = {http://arxiv.org/abs/0709.0099}, year = {2007} }

RIS record

TY - ELEC ID - citeulike:2575181 L3 - citeulike-article-id:2575181 TI - The road coloring problem N2 - The synchronizing word of 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 deterministic finite automaton possessing a synchronizing word. The road coloring problem is a problem of synchronizing coloring of 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 a noticeable interest among the specialists in theory of graphs, deterministic automata and symbolic dynamics. The problem is described even in "Wikipedia" - the popular Internet Encyclopedia. The positive solution of the road coloring problem is presented. KW - automata KW - combinatorics KW - graph KW - maths AU - Trahtman, AN PY - 2007/Dec/21/ UR - http://arxiv.org/abs/0709.0099 ER -

RIS BibTeX