8
$\begingroup$

The Cerny conjecture is the statement that any synchronizing automaton with $n$ states has a synchronizing word of length at most $(n-1)^2$. The best current upper bound for the length of a synchronizing word is $O(n^3)$. Let's say that two states are merged by a word if that word takes the two states to the same state. A pumping lemma type argument shows that in a synchronizing automaton, any two states can be merged by a word of length at most $n^2$. Suppose that the following conjecture is true.

Conjecture. Any subset of $k$ states contains two states that can be merged by a word of length (say) at most $n^2/k$. Or more generally, any large set of states contains two that can be merged by a word of length $o(n^2)$.

Then we can consider the following strategy for constructing a synchronizing word. We start with all $n$ states. By the conjecture above, there is a short word merging two states, and we make this the beginning of our synchronizing word. We can run the DFA with this word starting from all states, and we get a set of at most $n-1$ final states. We repeat this with these final states as our new start states. After repeating this a sufficient number of times, we only end up with one final state. Clearly, given the above conjecture, we would have a better bound than $O(n^3)$ for the length of the shortest synchronizing word.

The above motivates the following questions:

  1. Are there any known counterexamples to this conjecture? Cerny's original construction (see page 18) satisfies the statement of the conjecture.
  2. Could you provide a reference where similar ideas are investigated?
$\endgroup$
1
$\begingroup$

I found a partial answer to question 2. The same idea is discussed in the last 10 minutes of this lecture.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.