A QUADRATIC UPPER BOUND ON THE SIZE OF A SYNCHRONIZING WORD IN ONE-CLUSTER AUTOMATA
Cerny's conjecture asserts the existence of a synchronizing word of length at most (n - 1)(2) for any synchronized n-state deterministic automaton. We prove a quadratic upper bound on the length of a synchronizing word for any synchronized n-state deterministic automaton satisfying the following additional property: there is a letter a such that for any pair of states p, q, one has p.a(r) = q.a(s) for some integers r, s (for a state p and a word w, we denote by p.w the state reached from p by the path labeled w). As a consequence, we show that for any finite synchronized prefix code with an n-state decoder, there is a synchronizing word of length O(n(2)). This applies in particular to Huffman codes.
cerny's conjecture road coloring problem synchronized automata