# Problems on Finite Automata and the Exponential Time Hypothesis
## 3 The Non-Tally Case
Also, as argued below, the automaton can accept all words longer than \(n\), starting with an improper coloring coding of the word, as this can drive the automaton into state \(f\). Further, our construction enables the check of an improper coloring. A coloring is improper if to vertices that are connected have the same color, so we should accept a word \(w=w_{1}\ldots w_{n}\) iff \(i<j\) and \((i,j)\in E\) and \(w_{i}=w_{j}\). Pick such a word and assume, without a loss of generality, that \(w_{i}=a\). Then the automaton will accept \(w\), since the additional edge \(q_{i}\stackrel{{ a}}{{\longrightarrow}}a_{j-i}\) allows for an accepting run terminating in the state \(f\). Note that the automaton accepts all words of length at most \(n-1\). Also, it accepts a word of length at least \(n\) iff the prefix of length \(n\) corresponds to a bad coloring. Hence the automaton accepts all words iff all colorings are bad. The converse direction is also easily seen. Assume there is a valid coloring represented by a word \(w_{1}\ldots w_{n}\). Assume by contradiction that this word is accepted by the automaton. As the word has length \(n\) an accepting run has to terminate in \(f\), and so one of the edges added to the automaton backbone as shown in Figure 1 has to be part of this run. Assume, without a loss of generality, that this is the edge \(q_{i}\stackrel{{ a}}{{\longrightarrow}}a_{j-i}\). Then \(w_{i}=a\), as the edge was chosen and since this run leads to \(f\), also the letter at position \(i+(j-i)\) has to equal \(a\). However, as \((i,j)\in E\) this is not valid coloring, hence the assumption that the word is accepted by the automaton was false. Hence, if there is a valid coloring the automaton does not accept all words. It is simple to change the construction given above to get away with binary input alphabets (instead of ternary ones), for instance, by encoding \(a\) as \(00\), \(b\) as \(01\) and \(c\) as \(10\). We are now turning towards DFA-Intersection and also to NFA-Intersection. In the classical perspective, both are PSPACE-complete problems. An adaptation of our preceding reduction from 3-Coloring, considering \(|E|\) DFAs each with \(3|V|+1\) states obtained from a graph instance \((V,E)\), yields the next result, where upper and lower bounds perfectly match. In the following proposition we have parameters \(k\) the number of automata, \(q\) the maximum size of these automata, and \(n\) the input length. The parameters \(k,q\) are both upper bounded by \(n\). Recall that the notation \(O^{*}(2^{f(k,q)})\) drops polynomial factors in \(n\) even though \(n\) is not explicitly mentioned in the expression. Figure 1: A sketch of the NFA construction of Theorem 4. **Proposition 2**. : _There is no algorithm that, given \(k\) DFAs (or NFAs) \(A_{1},\ldots,A_{k}\) with arbitrary input alphabet, each with at most \(q\) states, decides if \(\bigcap_{i=1}^{k}L(A_{i})=\emptyset\) in time \(O^{*}\left(2^{\log(q)\cdot o(k)}\right)\) unless ETH fails. Conversely, there is an algorithm that, given \(k\) DFAs (or NFAs) \(A_{1},\ldots,A_{k}\) with arbitrary input alphabet, each with at most \(q\) states, decides if \(\bigcap_{i=1}^{k}L(A_{i})\
eq\emptyset\) in time \(O^{*}\left(2^{\log(q)\cdot k}\right)\)._  
Proof. : The hardness is by adaptation of the the 3-Coloring reduction we gave for Universality. For parameters \(k\) and \(q\), we take a graph with \(|V|+|E|=k\log_{3}q=\Theta(k\log q)\). In this proof, we neglect the use of some ceiling functions for the sake of readability. For the DFAs, choose the alphabet \(\Sigma=V\times C\), \(C=\{1,2,3\}\). The states are \(s,t,\bot\). For each vertex \(v\), we define the DFA \(A_{v}\), and for each edge \(uv\) and each color \(a\), we define the DFA \(A_{uv,a}\), as described in Figure 2. Clearly, we have \(|V|+|E|\) many of these DFAs \(A_{i}\). We can compute the intersection for each block of \(\log_{3}q\) automata into a single DFA in polynomial time (with respect to \(q\)). This can be most easily seen by performing a multi-product construction.