Synchronizing automata on quasi-Eulerian digraph

Abstract

We describe a new version of the so-called extension method that was used to prove quadratic upper bounds on the minimum length of reset words for various important classes of synchronizing automata. Our approach is formulated in terms of Markov chains; it is in a sense dual to the usual extension method and improves on a recent result by Jungers. As an application, we obtain a quadratic upper bound on the minimum length of reset words for a generalization of Eulerian automata. © 2012 Springer-Verlag.