User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

Dynamics of the Independence Number and Automata Synchronization

Primary tabs

Gusev, Vladimir [UCL] Jungers, Raphaël M. [UCL] Průša, Daniel

We study the lengths of synchronizing words produced by the classical greedy compression algorithm. We associate a sequence of graphs with every synchronizing automaton and rely on evolution of the independence number to bound the lengths of produced words. By leveraging graph theoretical results we show that in many cases automata with good extension properties have good compression properties as well. More precisely, we show that the compression algorithm will produce a synchronizing word of length O(n2log(n)) on cyclic, regular and strongly-transitive automata with n states, which is not far from the best possible bound of (n−1)2. Furthermore, we provide a relatively simple proof that every n-state automaton has a synchronizing word of length at most n34+O(n2).

Document type Communication à un colloque (Conference Paper) – Présentation orale avec comité de sélection
Publication date 2018
Language Anglais
Conference "DLT 2018", Tokyo, Japan (du 10/09/2018 au 14/09/2018)
Peer reviewed yes
Host document "Developments in Language Theory : Lecture Notes in Computer Science"- p. 379-391 (ISBN : 9783319986531)
Publication status Publié
Affiliation UCL - SST/ICTM/INMA - Pôle en ingénierie mathématique
Links
  1. Adler Roy L., Goodwyn L. Wayne, Weiss Benjamin, Equivalence of topological Markov shifts, 10.1007/bf02761605
  2. Ananichev Dimitry S., Gusev Vladimir V., Approximation of Reset Thresholds with Greedy Algorithms, 10.3233/fi-2016-1357
  3. Araújo João, Cameron Peter, Steinberg Benjamin, Between primitive and 2-transitive: Synchronization and its friends, 10.4171/emss/4-2-1
  4. BÉAL MARIE-PIERRE, BERLINKOV MIKHAIL V., PERRIN DOMINIQUE, A QUADRATIC UPPER BOUND ON THE SIZE OF A SYNCHRONIZING WORD IN ONE-CLUSTER AUTOMATA, 10.1142/s0129054111008039
  5. Berlinkov, M.V., Ferens, R., Szykuła, M.: Extending word problems in deterministic finite automata. CoRR abs/1704.08233 (2017)
  6. Berlinkov Mikhail V., Szykuła Marek, Algebraic synchronization criterion and computing reset words, 10.1016/j.ins.2016.07.049
  7. Berstel, J., Perrin, D., Reutenauer, C.: Codes and Automata. Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge (2009)
  8. Carpi Arturo, D’Alessandro Flavio, Strongly transitive automata and the Černý conjecture, 10.1007/s00236-009-0106-7
  9. Černý, J.: Poznámka k homogénnym experimentom s konečnými automatmi. Matematicko-fyzikálny Časopis Slovenskej Akadémie Vied 14(3), 208–216 (1964)
  10. Chevalier Pierre-Yves, Hendrickx Julien M., Jungers Raphael M., Reachability of consensus and synchronizing automata, 10.1109/cdc.2015.7402864
  11. Dubuc L., Sur les automates circulaires et la conjecture de Černý, 10.1051/ita/1998321-300211
  12. Eppstein David, Reset Sequences for Monotonic Automata, 10.1137/0219033
  13. Gawrychowski Paweł, Straszak Damian, Strong Inapproximability of the Shortest Reset Word, Mathematical Foundations of Computer Science 2015 (2015) ISBN:9783662480564 p.243-255, 10.1007/978-3-662-48057-1_19
  14. Gerbush Michael, Heeringa Brent, Approximating Minimum Reset Sequences, Implementation and Application of Automata (2011) ISBN:9783642180972 p.154-162, 10.1007/978-3-642-18098-9_17
  15. Gerencsér Balázs, Gusev Vladimir V., Jungers Raphaël M., Primitive Sets of Nonnegative Matrices and Synchronizing Automata, 10.1137/16m1094099
  16. Gonze François, Gusev Vladimir V., Gerencsér Balázs, Jungers Raphaël M., Volkov Mikhail V., On the Interplay Between Babai and Černý’s Conjectures, Developments in Language Theory (2017) ISBN:9783319628080 p.185-197, 10.1007/978-3-319-62809-7_13
  17. Graham, R.L., Grötschel, M., Lovász, L. (eds.): Handbook of Combinatorics, vol. 2. MIT Press, Cambridge (1995)
  18. Kari Jarkko, Synchronizing finite automata on Eulerian digraphs, 10.1016/s0304-3975(02)00405-x
  19. Klyachko, A.A., Rystsov, I.K., Spivak, M.A.: An extremal combinatorial problem associated with the bound on the length of a synchronizing word in an automaton. Kibernetika 2, 16–20 (1987)
  20. Pin J.E., On two Combinatorial Problems Arising from Automata Theory, Combinatorial Mathematics, Proceedings of the International Colloquium on Graph Theory and Combinatorics (1983) ISBN:9780444865120 p.535-548, 10.1016/s0304-0208(08)73432-7
  21. Roman Adam, Szykuła Marek, Forward and backward synchronizing algorithms, 10.1016/j.eswa.2015.07.071
  22. Rystsov I. K., Almost optimal bound of recurrent word length for regular automata, 10.1007/bf02366314
  23. Rystsov, I.K.: On the length of reset words for automata with simple idempotents. Kibernet. Sistem. Anal. 187(3), 32–39 (2000)
  24. Salomaa Arto, Composition sequences for functions over a finite domain, 10.1016/s0304-3975(01)00227-4
  25. STEINBERG BENJAMIN, THE AVERAGING TRICK AND THE ČERNÝ CONJECTURE, 10.1142/s0129054111008970
  26. Szykuła, M.: Improving the upper bound on the length of the shortest reset word. In: Niedermeier, R., Vallée, B. (eds.) Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics, vol. 96, pp. 56:1–56:13. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Germany (2018)
  27. Trahtman A. N., The road coloring problem, 10.1007/s11856-009-0062-5
  28. Volkov Mikhail V., Synchronizing Automata and the Černý Conjecture, Language and Automata Theory and Applications ISBN:9783540882817 p.11-27, 10.1007/978-3-540-88282-4_4
Bibliographic reference Gusev, Vladimir ; Jungers, Raphaël M. ; Průša, Daniel. Dynamics of the Independence Number and Automata Synchronization.DLT 2018 (Tokyo, Japan, du 10/09/2018 au 14/09/2018). In: Developments in Language Theory : Lecture Notes in Computer Science, 2018, p. 379-391
Permanent URL http://hdl.handle.net/2078.1/203244