<p>see ArXiv:
1405.2435   cs.FL   "The length of a minimal synchronizing word and the \v{C}erny conjecture" with the story of study
 <a href="https://arxiv.org/pdf/1405.2435.pdf" rel="nofollow noreferrer">https://arxiv.org/pdf/1405.2435.pdf</a></p>

CC BY-SA 3.0
2017-06-09T12:57:08.120Z
It would be better to summarize the main claim(s) of the paper -- this is otherwise a link-only answer.
chi
CC BY-SA 4.0
2019-04-06T00:53:17.317Z
Made worse by the fact that the link is broken.
domotorp
CC BY-SA 3.0
2017-06-09T06:33:45.590Z
2017-06-09T06:33:45.590Z
trahtman
<p>Trakhtman has a <a href="http://u.cs.biu.ac.il/~trakht/syn.html">bibliography</a> on the problem, which is apparently kept up to date; so I suppose Černý's question remains unresolved until today. The same is stated in Volkov's recent <a href="http://csseminar.kadm.usu.ru/tarragona_volkov2008.pdf">survey</a> (LATA 2008) linked from the wikipedia article cited in the question. There you find pointers to some partial results, for example, for which subclasses of regular languages the conjecture is known to be true. Even more recent is a <a href="http://arxiv.org/abs/1005.0129">research paper</a> by Ananichev, Gusev &amp; Volkov (MFCS 2010) on a related topic, where they confirm that Černý's conjecture is still open now (at least as of May 2010).</p>

CC BY-SA 3.0
2013-09-28T20:47:10.143Z
In 2012, Trahtman uploaded a [paper](http://arxiv.org/abs/1202.4626) to arXiv, where he presents an effort to solve the conjecture. This was more than a year ago. Is there any news on the correctness of the proof?
molnarg
CC BY-SA 3.0
2014-07-20T11:32:23.710Z
In the comment section on the current version (v7) of the arXiv preprint, the author states "13 pages, examples, wrong version. The proof of the Černý conjecture is wrong": http://arxiv.org/abs/1202.4626
Hermann Gruber
CC BY-SA 2.5
2010-11-25T21:30:08.467Z
2010-11-25T21:30:08.467Z
Hermann Gruber
<p>A DFA has a <a href="http://en.wikipedia.org/wiki/Synchronizing_word">synchronizing word</a> if there is a string that sends any state of the DFA to a single state. In ‘The Cerny Conjecture for Aperiodic Automata” by A. N. Trahtman (Discrete Mathematics and Theoretical Computer Science vol. 9:2, 2007, pp.3-10), he wrote,</p>

<blockquote>
  <p>Cerny conjectured in 1964 that every
  n-state synchronizable DFA possesses a
  synchronizing word of length at most
  $(n-1)^2$.</p>
</blockquote>

<p>He also wrote, "in the case when the underlying graph of the aperiodic DFA is strongly connected, this upper bound has been recently improved by Volkov who has reduced the estimation to $n(n + 1)/6$.</p>

<ol>
<li><p>Does anybody know the current status of Cerny conjecture?</p></li>
<li><p>And in which paper Volkov obtained the result n(n+1)/6 ?</p></li>
</ol>

<p>Thanks for any pointer or link.</p>

CC BY-SA 2.5
2010-11-25T13:13:52.157Z
After I posted the question, I did a search and found the answer of my second question, in which paper Volkov obtained the result n(n+1)/6?

The answer is
‘Synchronizing Automata Preserving a Chain of Partial Orders’
Lecture Notes in Computer Science, 2007, Volume 4783/2007, 27-37, DOI: 10.1007/978-3-540-76336-9_5
Nobody
CC BY-SA 2.5
2010-11-25T17:40:36.007Z
you can edit the question to reflect this.
Suresh Venkat
<fl.formal-languages><automata-theory><open-problem><synchronization>
Status of Cerny Conjecture?
Nobody
# Status of Cerny Conjecture?

(Asked by: username_0 on 2010-11-25)

A DFA has a [synchronizing word](http://en.wikipedia.org/wiki/Synchronizing_word) if there is a string that sends any state of the DFA to a single state. In ‘The Cerny Conjecture for Aperiodic Automata” by A. N. Trahtman (Discrete Mathematics and Theoretical Computer Science vol. 9:2, 2007, pp.3-10), he wrote,

> Cerny conjectured in 1964 that every
> n-state synchronizable DFA possesses a
> synchronizing word of length at most
> $(n-1)^2$.

He also wrote, "in the case when the underlying graph of the aperiodic DFA is strongly connected, this upper bound has been recently improved by Volkov who has reduced the estimation to $n(n + 1)/6$.

1. Does anybody know the current status of Cerny conjecture?
2. And in which paper Volkov obtained the result n(n+1)/6 ?

Thanks for any pointer or link.

**Tags:** fl.formal-languages, automata-theory, open-problem, synchronization
> **Comments:**
> **username_0**: After I posted the question, I did a search and found the answer of my second question, in which paper Volkov obtained the result n(n+1)/6?  The answer is ‘Synchronizing Automata Preserving a Chain of Partial Orders’ Lecture Notes in Computer Science, 2007, Volume 4783/2007, 27-37, DOI: 10.1007/978-3-540-76336-9_5  
> **username_1**: you can edit the question to reflect this.  

---

## 2 answers

### Answer by username_5 on 2010-11-25. Score: 19 | Accepted answer

Trakhtman has a [bibliography](http://u.cs.biu.ac.il/~trakht/syn.html) on the problem, which is apparently kept up to date; so I suppose Černý's question remains unresolved until today. The same is stated in Volkov's recent [survey](http://csseminar.kadm.usu.ru/tarragona_volkov2008.pdf) (LATA 2008) linked from the wikipedia article cited in the question. There you find pointers to some partial results, for example, for which subclasses of regular languages the conjecture is known to be true. Even more recent is a [research paper](http://arxiv.org/abs/1005.0129) by Ananichev, Gusev & Volkov (MFCS 2010) on a related topic, where they confirm that Černý's conjecture is still open now (at least as of May 2010).

> **Comments:**
> **username_6**: In 2012, Trahtman uploaded a [paper](http://arxiv.org/abs/1202.4626) to arXiv, where he presents an effort to solve the conjecture. This was more than a year ago. Is there any news on the correctness of the proof?  
> **username_5**: In the comment section on the current version (v7) of the arXiv preprint, the author states "13 pages, examples, wrong version. The proof of the Černý conjecture is wrong": http://arxiv.org/abs/1202.4626  

---

### Answer by username_2 on 2017-06-09. Score: 3

see ArXiv:
1405.2435 cs.FL "The length of a minimal synchronizing word and the \v{C}erny conjecture" with the story of study
<https://arxiv.org/pdf/1405.2435.pdf>

> **Comments:**
> **username_3**: It would be better to summarize the main claim(s) of the paper -- this is otherwise a link-only answer.  
> **username_4**: Made worse by the fact that the link is broken.  

---

