On Cerný’s conjecture for synchronizing automata
29/04/2016 29 Abril, 16h30, 6.2.33
Jorge Orestes Cerdeira (DM & CMA/FCT/UNL)
Faculdade de Ciências da Universidade de Lisboa
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)2.