The Černy conjecture

Details The Černy conjecture The Černy conjecture

2012-02-21

arxiv.org/abs/1202.4626v3

Computer Science

Discrete Mathematics

10 pages, main lemma is untrue, the proof is wrong

Scientific paper

A word w is called a synchronizing word of deterministic finite automaton (DFA) if w sends all states of the automaton to a unique state. In 1964, Jan Cerny discovered a sequence of an n-state complete DFA possessing a minimal synchronizing word of length (n-1)^2. The Cerny conjecture claims that it is also the upper bound on the length of such a word for a complete DFA. The problem has motivated great and constantly growing number of investigations and generalizations and together with the Road Coloring problem is considered as a most fascinating old problem in the theory of finite automata. The recently known upper bound for the length of the shortest synchronizing word is now equal to n(7n^2+6n-16)/48. An effort to prove the \v{C}erny conjecture is presented.

Affiliated with

Also associated with

No associations

Rating

The Černy 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 Černy conjecture, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Černy conjecture will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-423498