On Cerný’s conjecture for synchronizing automata

A deterministic finite automaton with n states is called synchronizing if there is a sequence of letters which maps the n states onto a single one. In this talk I will give a proof that searching for a synchronizing word of minimum length is NP-hard, and derive a network flow version of Cerný’s conjecture which states that for every synchronizing automata there is a synchronizing word of length at most (n-1)².