Modifying the upper bound on the length of minimal synchronizing word

Details Modifying the upper bound on the length of minimal synchronizing word Modifying the upper bound on the length of minimal synchronizing word

2011-04-13

arxiv.org/abs/1104.2409v4

Computer Science

Discrete Mathematics

8 pages

Scientific paper

A word $w$ is called synchronizing (recurrent, reset, magic, directable) word of deterministic finite automaton (DFA) if $w$ sends all states of the automaton to a unique state. In 1964 Jan \v{C}erny found a sequence of n-state complete DFA possessing a minimal synchronizing word of length $(n-1)^2$. He conjectured that it is an upper bound on the length of such words for complete DFA. Nevertheless, the best upper bound $(n^3-n)/6$ was found almost 30 years ago. We reduce the upper bound on the length of the minimal synchronizing word to $n(7n^2+6n-16)/48$. An implemented algorithm for finding synchronizing word with restricted upper bound is described. The work presents the distribution of all synchronizing automata of small size according to the length of an almost minimal synchronizing word.

Affiliated with

Also associated with

No associations

Rating

Modifying the upper bound on the length of minimal synchronizing word 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 Modifying the upper bound on the length of minimal synchronizing word, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Modifying the upper bound on the length of minimal synchronizing word will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-217842