# Problems on Finite Automata and the Exponential Time Hypothesis
## 2 Universality, Equivalence, Intersection: Unary Inputs
Let us mention that there have been indeed proposal for different algorithms to test universality for NFAs; we only refer to [12], but we are not aware of any accompanying complexity analysis that shows the superiority of that approach over the classical one. Conversely, it might be possible to tighten the upper bound. Notice that this problem is trivial for tally DFAs by state complementation and hence reduction to the polynomial-time solvable emptiness problem. We now turn to the equivalence problem for tally NFAs. As an easy corollary from Theorem 2, we obtain the next result. Corollary 1: _Unless ETH fails, there is no \(O^{*}\left(2^{o(q^{1/3})}\right)\)-time algorithm for deciding equivalence of two NFAs \(A_{1}\) and \(A_{2}\) on at most \(q\) states and input alphabet \(\{a\}\)._  
We are finally turning towards Tally-DFA-Intersection and also towards Tally-NFA-Intersection. CoNP-completeness of this problem, both for DFAs and for NFAs, was indicated in [13], referring to [9; 14]. We make this more explicit in the following, in order to also obtain some ETH-based results. Theorem 3: _Let \(k\) tally DFAs \(A_{1},\ldots,A_{k}\) with input alphabet \(\{a\}\) be given, each with at most \(q\) states. If ETH holds, then there is no algorithm with that decides if \(\bigcap_{i=1}^{k}L(A_{i})=\emptyset\) in time \(O^{*}\left(2^{o(\min(k\sqrt{\log q},\sqrt{q}))}\right)\)._  
Proof: We revisit our previous reduction (from an instance \(G=(V,E)\) of 3-Coloring with \(|V|=n\) and \(|E|=m\) to some NFA instance for Universality), which delivered the union of many simple sets \(L_{i}\), each of which can be accepted by a DFA \(A_{i}\) whose automaton graph is a simple cycle. These DFAs \(A_{i}\) have \(O(n^{2})\) states each. The complements \(\overline{L_{i}}\) of these languages can be also accepted by DFAs \(\overline{A_{i}}\) of the same size. Ignoring constants, originally the union of \(O(n+m)\) many such sets was formed. Considering now the intersection of the complements of the mentioned simple sets, we obtain a lower bound if \(k\geqslant n+m\) and \(q\geqslant n^{2}\) or, a bit weaker, if \(q\geqslant(n+m)^{2}\). Finally, we can always merge two automata into one using the product construction. This allows us to halve the number of automata while squaring the size of the automata. This trade-off allows to optimize the values for \(k\) and \(q\). Assume we have an algorithm with running time \(2^{o(k\sqrt{\log q})}\), then we get can reduce 3-Coloring with \(m\) edges to intersection of \((n+m)/\log(n+m)\) automata each of size bounded by \(((n+m)^{2})^{\log(n+m)}=2^{2\log^{2}(n+m)}\), and hence solving it in time \(2^{o((n+m)/\log(n+m)\cdot\sqrt{2\log^{2}(n+m)})}=2^{o(n+m)}\), a contradiction. Similarly, there can be no algorithm with running time \(2^{o(\sqrt{q})}\). Proposition 1: _Let \(k\) tally DFAs \(A_{1},\ldots,A_{k}\) with input alphabet \(\{a\}\) be given, each with at most \(q\) states. There is an algorithm that decides if \(\bigcap_{i=1}^{k}L(A_{i})=\emptyset\) in time \(O^{*}\left(2^{\min(k\log q,1.5\cdot q)}\right)\)._  
Proof: For the upper bound there are basically two algorithms; the natural approach to solve this intersection problem would be to first build the product automaton, which is of size \(q^{k}\), and then solve the emptiness problem in linear time on this device. This gives an overall running time of \(O^{*}\left(q^{k}\right)=O^{*}\left(2^{k\log q}\right)\); also see Theorem 8.3 in [15]. On the other hand, we can test all words up to length \(q+2^{1.5q}\). As each DFA has at most \(q\) states in each DFA, processing a word enters a cycle in at most \(q\) steps. Also the size of the cycle in each DFA is bounded by \(q\). The least common multiple of all integers bounded by \(q\), i.e., \(e^{\psi(q)}\), where \(\psi\) is the second Chebyshev function, is bounded by \(2^{1.5q}\); see Propositions 3.2 and 5.1. in [16]. This yields an upper bound \(O^{*}\left(2^{1.5q}\right)\) of the running time.