2015/11/29 by Gusev, Vladimir V., Pribavkina, Elena V.
#FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)
paper · doi:10.48550/arxiv.1511.09079
A coloring of a digraph with a fixed out-degree k is a distribution of k labels over the edges resulting in a deterministic finite automaton. An automaton is called synchronizing if there exists a word which sends all states of the automaton to a single state. In the present paper we study connections between spectral and synchronizing properties of digraphs. We show that if a coloring of a digraph is not synchronizing, then the stationary distribution of an associated Markov chain has a partition of coordinates into blocks of equal sum. Moreover, if there exists such a partition, then there exists a non-synchronizing automaton with such stationary distribution. We extend these results to bound the number of non-synchronizing colorings for digraphs with particular eigenvectors. We also demonstrate that the length of the shortest synchronizing word of any coloring is at most w2 - 3w + 3, where w is the sum of the coordinates of the integer principal eigenvector of the digraph.