The Visualization of the Road Coloring Algorithm in the package TESTAS

Details The Visualization of the Road Coloring Algorithm in the package TESTAS The Visualization of the Road Coloring Algorithm in the package TESTAS

2009-07-16

arxiv.org/abs/0907.2755v3

Computer Science

Discrete Mathematics

12 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

The Visualization of the Road Coloring Algorithm in the package TESTAS does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Visualization of the Road Coloring Algorithm in the package TESTAS, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Visualization of the Road Coloring Algorithm in the package TESTAS will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-621141