# Problems on Finite Automata and the Exponential Time Hypothesis
## 3 The Non-Tally Case
Hence, given a block of \(\log_{3}q\) automata \(A_{i}\) with transition function \(\delta_{i}\), we output the new block automaton \(A_{B}\) whose set of states \(Q_{B}\) corresponds to all (\(q\) many) ternary numbers, interpreted as \((\log_{3}q)\)-tuples in \(\{s,t,\bot\}^{\log_{3}q}\). We output a transition in the table of \(\delta_{B}\) in the following situation:  
\[\delta_{B}((p_{1},\ldots,p_{\log_{3}q}),(v,a))=\left(\delta_{1}(p_{1},(v,a)), \ldots,\delta_{\log_{3}q}(p_{\log_{3}q},(v,a))\right).\]  
So, we have to look up \(3q|\Sigma|\) times the tables of the \(A_{i}\)'s, where each of the \(\log_{3}q\) look-ups takes roughly \(3|\Sigma|\) time. This way, we obtain an automaton with \(q\) states and we reduce the number of DFAs to \(k=(|V|+|E|)/\log_{3}q\). Hence, we got \(k\) DFAs each with \(q\) states. If there was an algorithm solving DFA-Intersection in time \(O^{*}\left(2^{\log(q)o(k)}\right)\), then this would result in an algorithm solving 3-Coloring in time \(O^{*}\left(2^{o(|V|+|E|)}\right)\), contradicting ETH. Conversely, given \(k\) DFAs \(A_{1},\ldots,A_{k}\) with arbitrary input alphabet, each with at most \(q\) states (\(q\) is fixed), we can turn these into one DFA with \(O^{*}(q^{k})\) states by the well-known product construction, which allows us to solve the DFA-Intersection question in time \(O^{*}(2^{O(k\log q)})\). **Remark 2**. : _The proof of the previous theorem also implies that no such algorithm even if restricted to any infinite subset of tuples \((q,k)\subseteq\{3,4,\ldots\}\times\{1,2,3,\ldots\}\) in time \(O^{*}(2^{\log(q)o(k)})\) can exist, unless ETH fails. Especially, if \(q\) is fixed to a constant greater than 2, no algorithm in time \(O^{*}\left(2^{o(k)}\right)\) can exist, unless ETH fails._  
We can encode the large alphabet of the previous construction into the binary one, but we get a weaker result. In particular, the DFAs \(A_{v}\) and \(A_{uv,a}\) in this revised construction have \(O(\log n)\) states, and not constantly many as before. This means that we have to spell out the paths between the states \(s\) and \(t\), but this is not necessary with the trash state \(\bot\). Figure 2: The DFAs necessary to express a proper coloring. **Proposition 3**. : _There is no algorithm that, given \(k\) DFAs \(A_{1},\ldots,A_{k}\) with binary input alphabet, each with at most \(q\) states, decides if \(\bigcap_{i=1}^{k}L(A_{i})=\emptyset\) in time \(O^{*}\left(2^{o(k)}\right)\) or \(O^{*}\left(2^{o(2^{q})}\right)\), unless ETH fails._  
Proof. : We reduce this case to the case of unbounded alphabet size. Assume we are given \(k\) DFAs \(A_{1},\ldots,A_{k}\) over the alphabet \(\Sigma\), where \(|\Sigma|=l\). We encode each letter of \(\Sigma\) by a word of length \(\left\lceil\log l\right\rceil\) (block code) over the alphabet \(\left\{0,1\right\}\). In general, when converting an automaton from an alphabet \(\Sigma\) to an alphabet \(\left\{0,1\right\}\), the size of the automaton might increase by a factor of \(|\Sigma|\), as one might need to build a tree distinguishing all words of length \(\log l\). But we already know that, for the unbounded alphabet size, the lower bound is achieved by using only the automata from that proof (see Figure 2). These automata are special, as there are at most \(|C|=3\) many edges leaving each state, while all other edges loop. Hence, we only increase the number of states (and also edges) by a factor or \(4\log l\). The following proposition gives a matching upper bound:  
**Proposition 4**. : _There is an algorithm that, given \(k\) DFAs \(A_{1},\ldots,A_{k}\) with binary 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\min(k,2^{2}t)}\right)\)._  
Proof. : We will actually give two algorithms that solve this problem. One has a running time of \(O^{*}\left(2^{k\log q}\right)\) and one a running time of \(O^{*}\left(2^{2q\cdot\log q}\right)\). The result then follows.