The Cerny Conjecture

Details The Cerny Conjecture The Cerny Conjecture

2012-04-04

arxiv.org/abs/1204.0856v4

Computer Science

Formal Languages and Automata Theory

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

Scientific paper

The \v{C}ern\'y conjecture (\v{C}ern\'y, 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 \v{C}ern\'y conjecture is reduced to a simpler conjecture. In particular, we prove \v{C}ern\'y 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.

Affiliated with

Also associated with

No associations

Rating

The Cerny Conjecture does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Cerny Conjecture, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Cerny Conjecture will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-31351