# Problems on Finite Automata and the Exponential Time Hypothesis
## 4 Related Problems
### The Aperiodicity Problem
: _There is an algorithm for solving Aperiodicity that runs in time \(O^{*}\left(q^{q}\right)=O^{*}\left(2^{q\log q}\right)\) on a given \(q\)-state DFA with arbitrary input alphabet._  
Namely, first (as a preparatory step) create a table of size \(q^{q}\), classifying those mappings \(f:Q\to Q\) as _good_ that have the property that for some state \(p\) of the given DFA \(A\), \(f(p)\
eq p\) but \(f^{i}(p)=p\) for some \(i=2,\ldots,q\). The table creation needs time \(O^{*}\left(q^{q}\right)\). In a second column of our table, write down if a certain mapping \(f\) is _realizable_, i.e., does there exist a word \(w\in\Sigma^{*}\) such that \(\mu_{w}=f\)? In order to be able to reconstruct the word realizing \(f\), either notify that \(f\) is the identity (and hence \(f\) is realized as \(\mu_{e}\)), or write down a realizable map \(g\), i.e., \(g=\mu_{u}\) for some \(u\in\Sigma^{*}\), and a letter \(a\in\Sigma\), such that \(f=\mu_{ua}\). We build this second column by dynamic programming, starting with only one realizable entry, the identity, and then we keep looping through the whole alphabet (for all \(a\in\Sigma\)) and all realizable mappings \(g=\mu_{u}\) and mark \(f=\mu_{ua}\) as realizable until no further changes happen to the table. Hence, this part of the algorithm will perform at most \(q^{q}\) loops. Finally, we have to check in our table if there are any mappings that are both realizable and good. If so, we can construct a star witness, proving that \(L(A)\) is not aperiodic. If not, we know that the language \(L(A)\) is aperiodic. The overall running time of the algorithm is \(O^{*}\left(q^{q}\right)=O^{*}\left(2^{q\log q}\right)\). Another related problem asks whether, given a DFA \(A\), the language \(L(A)\) belongs to \(AC^{0}\), which means testing if \(L(A)\) is quasi-aperiodic.Let us make this more precise. Let \(L\subseteq\Sigma^{*}\) be a language, \(M\) be its syntactic monoid. and \(\eta:\Sigma^{*}\to L\) its syntactic morphism. A regular language is in \(\mathrm{AC}^{0}\) iff the syntactic morphism is quasi-aperiodic, i.e., for all \(n\in\mathbb{N}\) the subset \(\eta(\Sigma^{n})\) of \(M\) does not contain a non-trivial subgroup of \(M\). Analyzing the PSPACE-hardness proof of [PERSON], [PERSON] given in [26], we see that the same lower bound result as stated for Aperiodicity holds for this question, as well. We can reduce testing if the syntactic monoid of a language is aperiodic to the question whether the syntactic morphism is quasi-aperiodic by adding a neutral letter. This will give us the same lower bound as deciding aperiodicity. For the upper bound, note that we only need to test if \(\eta(\Sigma^{n})\) contains a group up to \(n\leq 2^{|M|}\). **Corollary 3**. : _Assuming ETH, there is no algorithm that runs in time \(O\left(2^{o(q)}\right)\) and decides, given a \(q\)-state DFA \(A\) on arbitrary input alphabets, whether or not the syntactic morphism of \(L(A)\) is quasi-aperiodic. Conversely, we can decide if a \(q\)-state automaton recognizes a language with a quasi-aperiodic syntactic morphism in time \(O^{*}(2^{q\log q})\)._  
It would be also interesting to study other \"hard subfamily problems\" for regular languages, as exemplified with [27], within the ETH framework. In addition, it would be also interesting to systematically study the complexity of the problems under scrutiny in the previous section, restricted to subclasses of regular languages, as we did in Claim 1 of the proof of Theorem 5.