<p>I found a partial answer to question 2. The same idea is discussed in the last 10 minutes of <a href="https://www.youtube.com/watch?v=0blZK9CewIc" rel="nofollow noreferrer">this lecture</a>.</p>

CC BY-SA 4.0
2019-04-09T02:43:04.393Z
2019-04-09T02:43:04.393Z
Kaarel Hänni
<p>The <a href="https://en.wikipedia.org/wiki/Synchronizing_word#Length" rel="noreferrer">Cerny conjecture</a> is the statement that any synchronizing automaton with <span class="math-container">$n$</span> states has a synchronizing word of length at most <span class="math-container">$(n-1)^2$</span>. The best current upper bound for the length of a synchronizing word is <span class="math-container">$O(n^3)$</span>. Let's say that two states are <em>merged</em> 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 <span class="math-container">$n^2$</span>. Suppose that the following conjecture is true.</p>

<p><strong>Conjecture.</strong> Any subset of <span class="math-container">$k$</span> states contains two states that can be merged by a word of length (say) at most <span class="math-container">$n^2/k$</span>. Or more generally, any large set of states contains two that can be merged by a word of length <span class="math-container">$o(n^2)$</span>.</p>

<p>Then we can consider the following strategy for constructing a synchronizing word. We start with all <span class="math-container">$n$</span> 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 <span class="math-container">$n-1$</span> 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 <span class="math-container">$O(n^3)$</span> for the length of the shortest synchronizing word.</p>

<p>The above motivates the following questions:</p>

<ol>
<li>Are there any known counterexamples to this conjecture? Cerny's original construction (see <a href="http://www.math.uni.wroc.pl/~kisiel/auto/volkov-surv.pdf" rel="noreferrer">page 18</a>) satisfies the statement of the conjecture.</li>
<li>Could you provide a reference where similar ideas are investigated?</li>
</ol>

<fl.formal-languages><automata-theory><open-problem><dfa><synchronization>
A conjecture related to the Cerny conjecture - counterexample/reference request
Kaarel Hänni
# A conjecture related to the Cerny conjecture - counterexample/reference request

(Asked by: username_0 on 2019-04-05)

The [Cerny conjecture](https://en.wikipedia.org/wiki/Synchronizing_word#Length) 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](http://www.math.uni.wroc.pl/~kisiel/auto/volkov-surv.pdf)) satisfies the statement of the conjecture.
2. Could you provide a reference where similar ideas are investigated?

**Tags:** fl.formal-languages, automata-theory, open-problem, dfa, synchronization


---

## 1 answers

### Answer by username_0 on 2019-04-09. Score: 1

I found a partial answer to question 2. The same idea is discussed in the last 10 minutes of [this lecture](https://www.youtube.com/watch?v=0blZK9CewIc).


---

