*Problem Definition:* Let \(A = (Q, \Sigma, \delta)\) be a (complete)
deterministic finite automaton (DFA) where \(Q\) is a finite set of states, \(\Sigma\) is
a finite alphabet and \(\delta \colon Q \times \Sigma \to Q\) is a (totally defined) transition
function (we neglect start and final states). We generalize \(\delta\) to words \(w=
w_1w_2 \dots w_n\), \(w_i \in \Sigma\) by setting \(\delta(q, w) = \delta(\delta(q, w_1)w_2\dots w_n)\). We
further generalize it to sets \(S\) of states by \(\delta(S, w) = \cup_{q\in S}\{\delta(q, w)\}\).
We say that a word \(w\in \Sigma^*\) is *synchronizing* for \(A\) if \(|\delta(Q, w)| = 1\),
i.e., regardless from which state we read \(w\), we end up in the same state.

We call a DFA *partial*, if \(\delta\) is a partial function. For a partial DFA
\(A\), we call a word \(w\in \Sigma^*\) *carefully* synchronizing, if \(|\delta(Q, w)|=1\)
and \(\delta(q, w)\) is defined fore each \(q\in Q\), i.e., we never try to use an
undefined transition when reading \(w\) from any state.

The problem of DFASyncCompletion asks, given a partial DFA \(A=(Q, \Sigma, \delta)\), is there a complete DFA \(A'=(Q, \Sigma, \delta')\) such that \(A'\) is synchronizing and \(\delta \subseteq \delta'\)?

*Open Question:* What is the complexity of DFASyncCompletion?

*Explanation & Comments:* Finding a synchronizing word for a
complete DFA can be done in polynomial time, but finding a carefully
synchronizing word for a partial DFA is PSPACE-complete.