# Problems on Finite Automata and the Exponential Time Hypothesis
## 6 Two Further Ways to Interpret Finite Automata
### Jumping Finite Automata
This also means (assuming P is not equal to NP) that there is no polynomial-time algorithm that computes, given a JFA \(A\), another JFA \(A^{\prime}\) that describes the Parikh mapping inverses of the complement of the Parikh images that \(A\) describes (otherwise, we would have a polynomial-time algorithm to solve Universality), nor is there a polynomial-time algorithm that computes, given two JFAs \(A_{1}\) and \(A_{2}\), a third JFA \(A_{3}\) such that the intersection of the (commutative / JFA) languages associated to \(A_{1}\) and \(A_{2}\) is just the language accepted by the JFA \(A_{3}\) (namely, otherwise we could solve the Universal Membership Problem in polynomial time; given a JFA \(A\) and a word \(w\), first construct a JFA \(A_{w}\) that accepts the permutation closure of \(\{w\}\) and then check if the intersection of the JFA languages of \(A\) and of \(A_{w}\) is empty). Recall that, by way of contrast, intersection is an easy operation even on NFAs. (This also indicates that the simple constructions for the corresponding closure properties of JFA languages as given in [36] are flawed.) However, the closure properties themselves hold true, as this was already known for the Parikh images of regular sets, also known as semi-linear sets, also see [42] and the references quoted therein. What about the three decidability questions that are central to this paper for these devices? As the behavior of JFA is the same as that of NFA on unary alphabets, we can borrow all results from Section 2. Let \(k=|\Sigma|\) be fixed. Unless ETH fails, there is no algorithm that solves Universality for \(q\)-state JFAs in time \(O^{*}\left(2^{o\left(q^{\frac{k}{q+2}}\right)}\right)\). **Proof. ** We only sketch the idea in the case of binary alphabets, i.e., when \(k=2\). We revisit our reduction from 3-Coloring for the case \(k=1\) detailed above. The main bottleneck was the coding of badly colored edges. This is taken care of in the following way. We encode the vertices \(v_{1},\ldots,v_{n}\) no longer by \(n\) prime numbers, but by pairs of \(\lceil\sqrt{n}\rceil\) many prime numbers, which are then expressed as powers of the input letters \(a\) and \(b\), resp. Hence, to describe the \(3m\) bad colorings of the \(m\) edges, we need no longer \(O(mn^{2})\) many states, but only \(O(mn)\) many. We can extend this method such that, for arbitrary \(k\), we would need \(O(mn^{\frac{k}{2}})\) many states for all bad edge colorings. \(\qed\)  
Notice that the expression that we claim somehow interpolates between the third root of \(q\) (in the exponent of 2), namely, when \(k=1\), and then it also coincides with our earlier findings, and \(q\) itself (if \(k\) tends to infinity). We could make the construction for arbitrary alphabets more explicit by re-interpreting the proof of Proposition 2 as one dealing with Universality for JFAs. **Proposition 6**: _Unless ETH fails, there is no algorithm that solves Universality for \(q\)-state JFAs in time \(O^{*}\left(2^{o(\sqrt{q})}\right)\)._  
**Proof. ** First observe that the DFAs \(A_{v}\) and \(A_{uv,a}\) that we constructed in the proof of Proposition 2 can be as well interpreted as JFAs, and also the automata \(\overline{A_{v}}\) and \(\overline{A_{uv,a}}\) that can be constructed by complementing the sets of final states can read the input in arbitrary sequence. It is easy to construct a JFA that accepts the union of all languages accepted by any JFA \(\overline{A_{v}}\) or \(\overline{A_{uv,a}}\). This union equals \(\Sigma^{*}\) (with \(\Sigma\) as in the referred proof) if and only if the given graph was not 3-colorable. \(\qed\)  
We can obtain very similar results for Equivalence for JFAs. Let us now briefly discuss Intersection. Interestingly enough, also the problem of detecting emptiness of the intersection of only two JFA languages is NP-hard. This and a related study on ETH-based complexity can be found in [37]. For the intersection of \(k\) JFAs, the proof of Proposition 2 actually shows the analogous result also in that case.