Synchronizing Automata on Quasi Eulerian Digraph

Abstract

In 1964 Černý conjectured that each $n$-state synchronizing automaton posesses a reset word of length at most $(n-1{)}^2$. From the other side the best known upper bound on the reset length (minimum length of reset words) is cubic in $n$. Thus the main problem here is to prove quadratic (in $n$) upper bounds. Since 1964, this problem has been solved for few special classes of \sa. One of this result is due to Kari \cite{Ka03} for automata with Eulerian digraphs. In this paper we introduce a new approach to prove quadratic upper bounds and explain it in terms of Markov chains and Perron-Frobenius theories. Using this approach we obtain a quadratic upper bound for a generalization of Eulerian automata.

arXiv comment8 pages, 1 figure