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$.Does anybody know the current status of Cerny conjecture?And in which paper Volkov obtained the result n(n+1)/6 ?Thanks for any pointer or link.
Status of Cerny Conjecture?
fl.formal languages;automata theory;open problem;synchronization
Trakhtman has a bibliography 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 (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 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).