# Problems on Finite Automata and the Exponential Time Hypothesis
## 6 Two Further Ways to Interpret Finite Automata
### Jumping Finite Automata  
A _jumping finite automaton_ (JFA) formally looks like a usual string-processing NFA. However, the application of a rule to a word is different: If \(p\xrightarrow{\ \ }p^{\prime}\) is a transition rule, then it can transform the input string \(u\) into \(u^{\prime}\) provided that \(u,u^{\prime}\) decompose as \(u=u_{1}au_{2}\) and \(u^{\prime}=u_{1}u_{2}\). In other words, a JFA may first jump to an arbitrary position of the input and then apply the rule there. This model wasintroduced in [36] and further studied in [37]. It is relatively easy to see that the languages accepted by JFAs are just the inverses of the Parikh images of the regular languages, or, in other words, the commutative (or permutation) closure of the regular languages, or, yet in different terminology, the inverses of the Parikh images of semilinear sets. In particular, the emptiness problem for JFAs is as simple as for NFAs. Also, for the case of unary input alphabets, JFAs and NFAs just work the same. Hence, Universality is hard for JFAs, as well. Classical complexity considerations on these formalisms are contained in [37; 38; 39; 40; 41]; observe that mostly the input is given in the form of Parikh vectors of numbers encoded in binary, while we will consider the input given in unary-encoded Parikh vectors below (namely, as words, i.e., as elements of the free monoid), since JFAs were introduced this way in [36]. Yet another way to formally look at how JFAs operate incorporates the use of the shuffle operation. Recall that \(w_{1}\shuffle w_{2}\) denotes the _shuffle_ of \(w_{1}\) and \(w_{2}\), which can be seen as observing a concurrent left-to-right read of \(w_{1}\) and \(w_{2}\), listing all possible concurrent reads. For instance, \(ab\shuffle ba=\{abba,abab,baba,baab\}\). Notice however that even if a JFA might formally look like a DFA, there is a certain nondeterminism inherent to this mechanism, which is the position at which the next symbol is read (in the case of non-unary input alphabets). It can be therefore shown that the uniform word problem for JFAs is NP-hard. Analyzing the proof given in [37], Theorem 54, we can conclude:  
Under ETH, there is no algorithm that, given a JFA \(A\) on \(q\) states and a word \(w\in\Sigma^{*}\), decides if \(w\in L(A)\) in time \(O^{*}\left(2^{o(q)}\right)\), \(O^{*}\left(2^{o\left(\frac{|w|}{|\Sigma|(q)}\right)}\right)\) nor \(O^{*}\left(2^{o\left(|\Sigma|\right)}\right)\). Notice that this problem can be solved in time \(O^{*}(n! )\) on arbitrary input alphabets, feeding all permutations of an input word of length \(n\) into the given automaton, interpreted as an NFA. There is also a dynamic programming algorithm solving Universal Membership for \(q\)-state JFAs (that is not improvable by Theorem 8, assuming ETH). This algorithm is based on the following idea. A word \(w\) allows the transition from state \(p\) to state \(p^{\prime}\) iff for some decomposition \(w\in w_{1}\shuffle w_{2}\), \(p\) can transfer to \(\hat{p}\) by reading \(w_{1}\) and from \(\hat{p}\) one can go into \(p^{\prime}\) when reading \(w_{2}\). For the correct implementation of the shuffle possibilities, we need to store possible translations for all subsets of indices within the input word, yielding a table (and time) complexity of \(O^{*}(2^{|w|})\). We have no other upper bound.