Synchronization of automata with one undefined or ambiguous transition

Abstract

We consider the careful synchronization of partial automata with only one undefined transition and the generalized synchronization of nondeterministic automata with only one ambiguous transition. For each of the two cases we prove that the problem of checking whether or not a given automaton is synchronizable is PSPACE-complete. The restrictions of these problems to 2-letter automata are also PSPACE-complete. © 2012 Springer-Verlag.