2022/06/14 by A. N. Trahtman, Trahtman, A. N.
Biochemistry, Genetics and Molecular Biology · Computer Science · #12Y99 #62A09 #Cellular Automata and Applications #DNA and Biological Computing #F.2.2 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #I.2.7 #K.6 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2206.07116
openalex publication_date 2022/06/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a finite directed graph, a coloring of its edges turns the graph into a finite-state automaton. A k-synchronizing word of a deterministic automaton is a word in the alphabet of colors at its edges that maps the state set of the automaton at least on k-element subset. A coloring of edges of a directed strongly connected finite graph of a uniform outdegree (constant outdegree of any vertex) is k-synchronizing if the coloring turns the graph into a deterministic finite automaton possessing a k-synchronizing word. For k=1 one has the well known road coloring problem. The recent positive solution of the road coloring problem implies an elegant generalization considered first by Beal and Perrin: a directed finite strongly connected graph of uniform outdegree is k-synchronizing iff the greatest common divisor of lengths of all its cycles is k. Some consequences for coloring of an arbitrary finite digraph are presented. We describe a subquadratic algorithm of the road coloring for the k-synchronization implemented in the package TESTAS. A new linear visualization program demonstrates the obtained coloring. Some consequences for coloring of an arbitrary finite digraph and of such a graph of uniform outdegree are presented.