The Cerny Conjecture

Abstract

The Černý conjecture (Černý, 1964) states that each n-state \san\ possess a \sw\ of length $(n-1{)}^2$. From the other side the best upper bound for the \rl\ of n-state \sa\ known so far is equal to $\frac{n^3-n}{6}$ (Pin, 1983) and so is cubic (a slightly better though still cubic upper bound $\frac{n(7n^2+6n-16)}{48}$ has been claimed in Trahtman but the published proof of this result contains an unclear place) in $n$. In the paper the Černý conjecture is reduced to a simpler conjecture. In particular, we prove Černý conjecture for one-cluster automata and quadratic upper bounds for automata closed to one-cluster automata. Our approach utilize theory of Markov chains and one simple fact from linear programming.

arXiv commentThis paper has been withdrawn by the author due to a crucial error in the proof of Corollary 2