Synchronizing Automata on Quasi Eulerian Digraph

2012/03/15 by Berlinkov, Mikhail V.
#F.4.1 #F.4.3 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)

paper · doi:10.48550/arxiv.1203.3402

Abstract

In 1964 Černý conjectured that each n-state synchronizing automaton posesses a reset word of length at most (n-1)². 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 \citeKa03 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.

Related

• A quadratic upper bound on the reset thresholds of synchronizing automata containing a transitive permutation group
• List of Results on the Černý Conjecture and Reset Thresholds for Synchronizing Automata
• An improvement to a recent upper bound for synchronizing words of finite automata
• Algebraic synchronization criterion and computing reset words
• Generating Synchronizing Automata with Large Reset Lengths