The Visualization of the Road Coloring Algorithm in the package TESTAS - Computer Science > Discrete MathematicsReportar como inadecuado




The Visualization of the Road Coloring Algorithm in the package TESTAS - Computer Science > Discrete Mathematics - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: A synchronizing word of a deterministic automaton is a word in the alphabetof colors of its edges that maps the automaton to a single state. A coloring ofedges of a directed graph is synchronizing if the coloring turns the graph intoa deterministic finite automaton possessing a synchronizing word.The road coloring problem is the problem of synchronizing coloring of adirected finite strongly connected graph with constant outdegree of all itsvertices if the greatest common divisor of the lengths of all its cycles isone. A polynomial time algorithm of the road coloring has been based on recentpositive solution of this old famous problem.One can use our new visualization program for demonstration of the algorithmas 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.



Autor: A.N. Trahtman, T. Bauer, N. Cohen

Fuente: https://arxiv.org/







Documentos relacionados