Document Open Access Logo

On Synchronizing Colorings and the Eigenvectors of Digraphs

Authors Vladimir V. Gusev, Elena V. Pribavkina

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2016.48.pdf
  • Filesize: 0.53 MB
  • 14 pages

Document Identifiers

Author Details

Vladimir V. Gusev
Elena V. Pribavkina

Cite As Get BibTex

Vladimir V. Gusev and Elena V. Pribavkina. On Synchronizing Colorings and the Eigenvectors of Digraphs. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 48:1-48:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.MFCS.2016.48

Abstract

An automaton is synchronizing if there exists a word that sends all states of the automaton to a single state. 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. The famous road coloring theorem states that every primitive digraph has a synchronizing coloring. We study recent conjectures claiming that the number of synchronizing colorings is large in the worst and average cases.

Our approach is based on the spectral properties of the adjacency matrix A(G) of a digraph G. Namely, we study the relation between the number of synchronizing colorings of G and the structure of the dominant eigenvector v of A(G). We show that a vector v has no partition of coordinates into blocks of equal sum if and only if all colorings of the digraphs associated with v are synchronizing. Furthermore, if for each b there exists at most one partition of the coordinates of v into blocks summing up to b, and the total number of partitions is equal to s, then the fraction of synchronizing colorings among all colorings of G is at least (k-s)/k. We also give a combinatorial interpretation of some known results concerning an upper bound on the minimal length of  synchronizing words in terms of v.

Subject Classification

Keywords
  • the road coloring problem
  • synchronizing automata
  • edge-colorings of digraphs
  • Perron-Frobenius eigenvector
  • primitive digraphs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. R. L. Adler, L. W. Goodwyn, and B. Weiss. Equivalence of topological Markov shifts. Israel Journal of Mathematics, 27(1):49-63, 1977. Google Scholar
  2. D. S. Ananichev, M. V. Volkov, and V. V. Gusev. Primitive digraphs with large exponents and slowly synchronizing automata. Journal of Mathematical Sciences, 192(3):263-278, 2013. Google Scholar
  3. M.-P. Béal and D. Perrin. Handbook of Formal Languages: Volume 2. Linear Modeling: Background and Application, chapter Symbolic Dynamics and Finite Automata, pages 463-506. Springer Berlin Heidelberg, 1997. Google Scholar
  4. M. V. Berlinkov. Synchronizing Automata on Quasi-Eulerian Digraph. In Implementation and Application of Automata, volume 7381 of LNCS, pages 90-100. Springer, 2012. Google Scholar
  5. M. V. Berlinkov. Synchronizing Quasi-Eulerian and Quasi-one-cluster Automata. International Journal of Foundations of Computer Science, 24(6):729-745, 2013. Google Scholar
  6. M. V. Berlinkov and M. Szykuła. Algebraic synchronization criterion and computing reset words. In Mathematical Foundations of Computer Science, volume 9234 of LNCS, pages 103-115. Springer, 2015. Google Scholar
  7. I. Borosh. A sharp bound for positive solutions of homogeneous linear Diophantine equations. Proc. Amer. Math. Soc., 60:19-21 (1977), 1976. Google Scholar
  8. A. Carpi and F. D'Alessandro. Independent sets of words and the synchronization problem. Advances in Applied Mathematics, 50(3):339-355, 2013. Google Scholar
  9. J. Černý. Poznámka k homogénnym experimentom s konečnými automatmi. Matematicko-fyzikálny Časopis Slovenskej Akadémie Vied, 14(3):208-216, 1964. In Slovak. Google Scholar
  10. K. Culik, J. Karhumäki, and J. Kari. A note on synchronized automata and road coloring problem. In Developments in Language Theory, volume 2295 of LNCS, pages 175-185. Springer, 2002. Google Scholar
  11. J. Friedman. On the Road Coloring Problem. Proceedings of the American Mathematical Society, 110(4):1133-1135, 1990. Google Scholar
  12. V. V. Gusev and E. V. Pribavkina. Reset thresholds of automata with two cycle lengths. International Journal of Foundations of Computer Science, 26(07):953-966, 2015. URL: http://dx.doi.org/10.1142/S0129054115400080.
  13. V. V. Gusev and M. Szykuła. On the number of synchronizing colorings of digraphs. In Implementation and Application of Automata, volume 9223 of LNCS, pages 127-139. Springer, 2015. Google Scholar
  14. J. Kari. Synchronizing finite automata on Eulerian digraphs. Theoretical Computer Science, 295(1-3):223-232, 2003. Google Scholar
  15. C. D. Meyer. Matrix Analysis and Applied Linear Algebra. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2000. Google Scholar
  16. B. Steinberg. The averaging trick and the Černý conjecture. International Journal of Foundations of Computer Science, 22(7):1697-1706, 2011. Google Scholar
  17. B. Steinberg. The Černý conjecture for one-cluster automata with prime length cycle. Theoretical Computer Science, 412(39):5487-5491, 2011. Google Scholar
  18. A. N. Trahtman. The Road Coloring Problem. Israel Journal of Mathematics, 172(1):51-60, 2009. Google Scholar
  19. M. V. Volkov. Synchronizing automata and the C̆erný conjecture. In Language and Automata Theory and Applications, volume 5196 of LNCS, pages 11-27. Springer, 2008. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact