Document Open Access Logo

On Randomized Generation of Slowly Synchronizing Automata

Authors Costanza Catalano, Raphaël M. Jungers

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2018.48.pdf
  • Filesize: 0.6 MB
  • 16 pages

Document Identifiers

Author Details

Costanza Catalano
  • Gran Sasso Science Institute, Viale Francesco Crispi 7, L'Aquila, Italy
Raphaël M. Jungers
  • ICTEAM Institute, UCLouvain, Avenue Georges Lemaîtres 4-6, Louvain-la-Neuve, Belgium

Funding

  • Jungers, Raphaël M.: R. M. Jungers is a FNRS Research Associate. He is supported by the French Community of Belgium, the Walloon Region and the Innoviris Foundation.

Cite As Get BibTex

Costanza Catalano and Raphaël M. Jungers. On Randomized Generation of Slowly Synchronizing Automata. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 48:1-48:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.MFCS.2018.48

Abstract

Motivated by the randomized generation of slowly synchronizing automata, we study automata made of permutation letters and a merging letter of rank n-1 . We present a constructive randomized procedure to generate synchronizing automata of that kind with (potentially) large alphabet size based on recent results on primitive sets of matrices. We report numerical results showing that our algorithm finds automata with much larger reset threshold than a mere uniform random generation and we present new families of automata with reset threshold of Omega(n^2/4) . We finally report theoretical results on randomized generation of primitive sets of matrices: a set of permutation matrices with a 0 entry changed into a 1 is primitive and has exponent of O(n log n) with high probability in case of uniform random distribution and the same holds for a random set of binary matrices where each entry is set, independently, equal to 1 with probability p and equal to 0 with probability 1-p , when np-log n - > infty as n - > infty .

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorics
  • Mathematics of computing → Random graphs
  • Theory of computation → Randomness, geometry and discrete structures
Keywords
  • Synchronizing automata
  • random automata
  • Cerný conjecture
  • automata with simple idempotents
  • primitive sets of matrices

Metrics

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

References

  1. N. Alon and J. H. Spencer. The Probabilistic Method. Wiley Publishing, 4th edition, 2016. Google Scholar
  2. Yu. Alpin and V. Alpina. Combinatorial properties of entire semigroups of nonnegative matrices. Journal of Mathematical Sciences, 207(5):674-685, 2015. Google Scholar
  3. 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
  4. M.-P. Béal, M. V. Berlinkov, and D. Perrin. A quadratic upper bound on the size of a synchronizing word in one-cluster automata. In International Journal of Foundations of Computer Science, pages 277-288, 2011. Google Scholar
  5. M.V. Berlinkov. On the Probability of Being Synchronizable, pages 73-84. Springer International Publishing, 2016. Google Scholar
  6. V.D. Blondel, R.M. Jungers, and A. Olshevsky. On primitivity of sets of matrices. Automatica, 61:80-88, 2015. Google Scholar
  7. Y.-B. Chen and D. J. Ierardi. The complexity of oblivious plans for orienting and distinguishing polygonal parts. Algorithmica, 14(5):367-397, 1995. Google Scholar
  8. P.-Y. Chevalier, J.M. Hendrickx, and R.M. Jungers. Reachability of consensus and synchronizing automata. In 4th IEEE Conference on Decision and Control, pages 4139-4144, 2015. Google Scholar
  9. M. de Bondt, H. Don, and H. Zantema. Dfas and pfas with long shortest synchronizing word length. In Developments in Language Theory, pages 122-133, 2017. Google Scholar
  10. D. Eppstein. Reset sequences for monotonic automata. SIAM Journal on Computing, 19(3):500-510, 1990. Google Scholar
  11. P. Frankl. An extremal problem for two families of sets. European Journal of Combinatorics, 3:125-127, 1982. Google Scholar
  12. B. Gerencsér, V. V. Gusev, and R. M. Jungers. Primitive sets of nonnegative matrices and synchronizing automata. Siam Journal on Matrix Analysis and Applications, 39(1):83-98, 2018. Google Scholar
  13. F. Gonze, B. Gerencsér, and R.M. Jungers. Synchronization approached through the lenses of primitivity. In 35th Benelux Meeting on Systems and Control, 2016. Google Scholar
  14. F. Gonze, V.V. Gusev, B. Gerencsér, R.M. Jungers, and M.V. Volkov. On the Interplay Between Babai and Černý’s Conjectures, pages 185-197. Springer International Publishing, 2017. Google Scholar
  15. V. V. Gusev and E. V. Pribavkina. Reset thresholds of automata with two cycle lengths. In Implementation and Application of Automata, pages 200-210, 2014. Google Scholar
  16. J. Kari. Synchronizing finite automata on eulerian digraphs. Theoretical Computer Science, 295(1):223-232, 2003. Google Scholar
  17. A. Kisielewicz and M. Szykuła. Synchronizing automata with extremal properties. In Mathematical Foundations of Computer Science 2015, pages 331-343, 2015. Google Scholar
  18. A. Mateescu and A. Salomaa. Many-valued truth functions, Černý’s conjecture and road coloring. In EATCS Bull., page 134–150, 1999. Google Scholar
  19. M. Michalina Dzyga, R. Ferens, V.V. Gusev, and M. Szykuła. Attainable values of reset thresholds. In 42nd International Symposium on Mathematical Foundations of Computer Science, volume 83, pages 40:1-40:14, 2017. Google Scholar
  20. C. Nicaud. Fast synchronization of random automata. In Approximation, Randomization, and Combinatorial Optimization, volume 60 of Leibniz International Proceedings in Informatics, pages 43:1-43:12, 2016. Google Scholar
  21. J. Olschewski and M. Ummels. The Complexity of Finding Reset Words in Finite Automata, pages 568-579. Springer Berlin Heidelberg, 2010. Google Scholar
  22. J.-E. Pin. On two combinatorial problems arising from automata theory. In Proceedings of the International Colloquium on Graph Theory and Combinatorics, volume 75, pages 535-548, 1983. Google Scholar
  23. V.Yu. Protasov and R.M. Jungers. Lower and upper bounds for the largest lyapunov exponent of matrices. Linear Algebra and its Applications, 438:4448-4468, 2013. Google Scholar
  24. V.Yu. Protasov and A.S. Voynov. Sets of nonnegative matrices without positive products. Linear Algebra and its Applications, 437:749-765, 2012. Google Scholar
  25. I. K. Rystsov. Estimation of the length of reset words for automata with simple idempotents. Cybernetics and Systems Analysis, 36(3):339-344, 2000. Google Scholar
  26. M. Szykuła. Improving the upper bound the length of the shortest reset words. In STACS, 2018. Google Scholar
  27. M. Szykuła and V. Vorel. An extremal series of eulerian synchronizing automata. In Developments in Language Theory, pages 380-392, 2016. Google Scholar
  28. J. Černý. Poznámka k homogénnym eksperimentom s konečnými automatami. Matematicko-fysikalny Casopis SAV, 14:208-216, 1964. Google Scholar
  29. M. V. Volkov. Synchronizing automata preserving a chain of partial orders. In Implementation and Application of Automata, pages 27-37, 2007. Google Scholar
  30. M.V. Volkov. Synchronizing automata and the Černý conjecture, volume 5196, 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