A linear algebra approach to synchronizing automata.

摘要

C˘erny's conjecture is a 40 years old open problem concerning the synchronizing of finite automata. Namely, it proposes an upper bound on the length of minimal synchronizing words for finite automata in terms of the number of states. So far, the conjecture has resisted proof except for some special cases of automata. We consider the following special cases: weakly orientable automata, Eulerian automata, and irreducible permutation automata.