Computational Complexity of Certain Problems Related to Carefully Synchronizing Words for Partial Automata and Directing Words for Nondeterministic Automata
We show that the problem of checking careful synchronizability of partial finite automata is PSPACE-complete. Also the problems of checking D 1-, D 2-, and D 3-directability of nondeterministic finite automata are PSPACE-complete; moreover, the restrictions of all these problems to automata with two input letters remain PSPACE-complete.
computational complexity synchronization automata directing words