Improved upper bounds on synchronizing nondeterministic automata

We show that i-directable nondeterministic automata can be i-directed with a word of length O(2ⁿ) for i=1,2, where n stands for the number of states. Since for i=1,2 there exist i-directable automata having i-directing words of length Ω(2ⁿ), these upper bounds are asymptotically optimal. We also show that a 3-directable nondeterministic automaton with n states can be 3-directed with a word of length , improving the previously known upper bound O(2ⁿ). Here the best known lower bound is .