On the interplay between Babai and Cerny's conjectures

François Gonze, Vladimir Gusev, Balázs Gerencsér +2

Motivated by the Babai conjecture and the Cerny conjecture, we study the reset thresholds of automata with the transition monoid equal to the full monoid of transformations of the…