On the Interplay Between Černý and Babai’s Conjectures
François Gonze, Vladimir V. Gusev, Raphaël M. Jungers, Balázs Szabolcs Gerencsér, Mikhail Vladimirovich Volkov · International Journal of Foundations of Computer Science · 2019
Motivated by the Babai conjecture and the Černý 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 [Formula: see text] states in this class, we prove that the reset threshold is upper-bounded by [Formula: see text] and can attain the value [Formula: see text]. In addition, we study diameters of the pair digraphs of permutation automata and construct [Formula: see text]-state permutation automata with diameter [Formula: see text].