# Problems on Finite Automata and the Exponential Time Hypothesis
## 4 Related Problems
### Synchronizing Words  
A deterministic finite semi-automaton (DFSA) \(A\) can be specified as \(A=(Q,\Sigma,\{\mu_{a}\mid a\in\Sigma\})\), where, for each \(a\in\Sigma\), there is a mapping \(\mu_{a}:Q\to Q\). Given some DFSA \(A\), a _synchronizing word_\(w\in\Sigma^{*}\) enjoys  
\[\forall p,p^{\prime}\in Q:\mu_{w}(p)=\mu_{w}(p^{\prime})\,.\]  
The Synchronizing Word (SW) problem is the question, given a DFSA \(A\) and an integer \(\ell\), whether there exists a synchronizing word \(w\) of length at most \(\ell\) for \(A\). This decision problem is related to the arguably most famous combinatorial conjecture in Formal Languages, which is [PERSON]'s conjecture [28], stating (in a relaxed form) that there is always a synchronizing word of size at most \(O(|Q|^{2})\) for any DFSA, should there be a synchronizing word at all.  
We have undertaken a multi-parameter analysis of this problem in [29]. The most straightforward parameters are \(|\Sigma|\), \(q=|Q|\), and an upper bound \(\ell\) on the length of the synchronizing word we are looking for. In [29], algorithms with running times of \(O^{*}(2^{q})\) and of \(O^{*}(|\Sigma|^{\ell})\) were given, complemented by proofs that show that there is neither an \(O^{*}(2^{o(q)})\)-time (with unbounded input alphabet size) nor an \(O^{*}((|\Sigma|-\epsilon)^{\ell})\)-time algorithm (for any \(\epsilon>0\)) under ETH or SETH, respectively.  
From the reduction presented in ([29] Theorem 12), we cannot get any lower bounds for bounded input alphabets; the dependency on \(\Sigma\) for the mentioned \(O^{*}(2^{q})\)-time algorithm is only linear.  
We were not able to answer this question completely for SW, but (only) for a more general version of this problem. Given a DFSA \(A=(Q,\Sigma,\{\mu_{a}\mid a\in\Sigma\})\) and a state set \(Q_{sync}\), a \(Q_{sync}\)-_synchronizing word_\(w\in\Sigma^{*}\) satisfies  
\[\forall p,p^{\prime}\in Q_{sync}:\mu_{w}(p)=\mu_{w}(p^{\prime})\,.\]  
The \(Q_{sync}\)-Synchronizing Word (\(Q_{sync}\)-SW) problem is the question, given a DFSA \(A\), a set of states \(Q_{sync}\) and an integer \(\ell\), whether there exists a \(Q_{sync}\)-synchronizing word \(w\) of length at most \(\ell\) for \(A\). Correspondingly, the \(Q_{sync}\)-Synchronizing Word problem can be stated. Notice that while SW is NP-complete, \(Q_{sync}\)-SW is even PSPACE-complete; see [30].  
Theorem 4.1: _There is an algorithm for solving \(Q_{sync}\)-SW on bounded input alphabets that runs in time \(O^{*}\left(2^{q}\right)\) for \(q\)-state deterministic finite semi-automata. Conversely, assuming ETH, there is no \(O^{*}\left(2^{o(q)}\right)\)-time algorithm for this task._  
Proof.: It was already observed in [29] that the algorithm given there for SW transfers to \(Q_{sync}\)-SW, as this is only a breadth-first search algorithm on an auxiliary graph (of exponential size, with vertex set \(2^{Q}\)). The PSPACE-hardness proof contained in ([30] Theorem 1.22), based on [31], reduces from DFA-Intersection. Given \(k\) automata each with at most \(s\) states, with input alphabet \(\Sigma\), one deterministic finite semi-automaton \(A=(Q,\{\mu_{a}\mid a\in\Sigma\})\) is constructed such that \(|Q|\leq sk+2\). Hence, an \(O^{*}\left(2^{o(|Q|)}\right)\)-time algorithm for \(Q_{sync}\)-SW would result in an \(O^{*}\left(2^{o(sk)}\right)\)-time algorithm for DFA-Intersection, contradicting Proposition 3.