# Status of Cerny Conjecture?

A DFA has a 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.

• 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 – scaaahu Nov 25 '10 at 13:13
• you can edit the question to reflect this. – Suresh Venkat Nov 25 '10 at 17:40