Synchronizing automata and principal eigenvectors of the underlying digraphs
| Autor: | Gusev, Vladimir V., Pribavkina, Elena V. |
|---|---|
| Rok vydání: | 2015 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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 $w^2 - 3w + 3$, where $w$ is the sum of the coordinates of the integer principal eigenvector of the digraph. Comment: 11 pages, preliminary version |
| Databáze: | arXiv |
| Externí odkaz: |
|