The complementation problem for nondeterministic word automata has numerous applications in formal verification In particular  the language-containment problem  to which many verification problems are reduced  involves complementation For automata on finite words  which correspond to safety properties  complementation involves determinization