Name
Abstract | ||
|---|---|---|
A synchronizing word of a deterministic automaton is a word in the alphabet
of colors 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 the lengths of all its cycles is
one. A polynomial time algorithm of the road coloring has been based on recent
positive solution of this old famous problem.
One can use our new visualization program for demonstration of the algorithm
as well as for visualization of the transition graph of any finite automaton.
The visual image presents some structure properties of the transition graph.
This help tool is linear in the size of the automaton. |
Year | Venue | Keywords |
|---|---|---|
2009 | Clinical Orthopaedics and Related Research | visualization,graph,dfa.,synchronization,road coloring,algorithm,connected graph,visual programming,deterministic finite automaton,greatest common divisor,directed graph,finite automaton |
Field | DocType | Volume |
Edge coloring,Discrete mathematics,Complete coloring,Combinatorics,Deterministic automaton,Fractional coloring,List coloring,Algorithm,Synchronizing word,Greedy coloring,Mathematics,Graph coloring | Journal | abs/0907.2 |
Citations | PageRank | References |
0 | 0.34 | 5 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| A. N. Trahtman | 1 | 92 | 11.68 |
| T. Bauer | 2 | 0 | 0.68 |
| N. Cohen | 3 | 0 | 0.34 |