On Cerný’s conjecture for synchronizing automata
29/04/2016 29 Abril, 16h30, 6.2.33
Jorge Orestes Cerdeira (DM & CMA/FCT/UNL)
Faculty of Sciences, University of Lisbon
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 NPhard, 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 (n1)^{2}.
