On the interplay between Babai and Cerny’s conjectures

Gonze, François;Gusev, Vladimir;Gerencser, Balazs;Jungers, Raphaël;Mikhail V. Volkov
(2018) international journal on foundation of computer science — (2018)

Files

170404047.pdf
  • Open Access
  • Adobe PDF
  • 272.7 KB
Download

Details

Authors
  • Gonze, FrançoisUCLouvain
    Author
  • Gusev, VladimirUCLouvain
    Author
  • Gerencser, BalazsAlfr´ed R´enyi Institute of Mathematics, Budapest, Hungary
    Author
  • Jungers, RaphaëlUCLouvain
    Author
  • Mikhail V. VolkovUral Federal University, Ekaterinburg, Russi
    Author
Abstract
Motivated by the Babai conjecture and the Cern´y conjecture, ˇ we study the reset thresholds of automata with the transition monoid equal to the full monoid of transformations of the state set. For automata with n states in this class, we prove that the reset thresholds are upperbounded by 2n 2 − 6n + 5 and can attain the value n(n−1) 2 . In addition, we study diameters of the pair digraphs of permutation automata and construct n-state permutation automata with diameter n 2 4 + o(n 2 ).
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Gonze, F., Gusev, V., Gerencser, B., Jungers, R., & Mikhail V. Volkov. (2018). On the interplay between Babai and Cerny’s conjectures. international journal on foundation of computer science. Accepted/in-press. https://hdl.handle.net/2078.5/251990 (Original work published 2018)