# Problems on Finite Automata and the Exponential Time Hypothesis
## 4 Related Problems
### The Aperiodicity Problem  
Recall that a regular language is called _star-free_ (or _aperiodic_) if it can be expressed, starting from finite sets, with the Boolean operations and with concatenation. (So, Kleene star is disallowed in the set constructions, in contrast to the 'usual' form of regular expressions.) We denote the subclass of the regular languages consisting of the star-free languages by \(\mathsf{SF}\). It is known that a language is star-free if and only it its syntactic monoid is aperiodic [21], that is, it does not contain any nontrivial group. Here we will use a purely automata-theoric characterization: A language accepted by some minimum-state DFA \(A\) is star-free iff for every input word \(w\), for every integer \(r\geqslant 1\) and for every state \(q\), \(\delta^{*}(q,w^{r})=q\) implies \(\delta^{*}(q,w)=q\). This allows a minimal automaton of a star-free language to contain a cycle, but if the non-empty word \(w\) along a cycle starting at \(q\) is a power of another non-empty word \(u\), i.e., \(w=u^{r}\) for some \(r\geqslant 2\), then \(u\) also forms a cycle starting at \(q\). For example, the language \(\{aaa\}^{*}\) is not aperiodic as \(a^{3}\) forms a cycle starting at any state of the minimal automaton, but \(a\) does not. However, \(\{abc\}^{*}\) is aperiodic, as \(abc,bca,cab\) are the only cycles in the minimal automaton (except for cycles starting at the sink state). For this class \(\mathsf{SF}\) (and in fact for any other subregular language class), one can ask the following decision problem. Given a DFA \(A\), is \(L(A)\in\mathsf{SF}\)? This problem (called Aperiodicity in the following) was shown to be PSPACE-complete by [PERSON] and [PERSON] in [22]. It relies on the following characterization of aperiodicity: [PERSON] and [PERSON] present a reduction that first (again) proves that the DFA-Intersection-Nonemptiness is PSPACE-complete (by giving a direct simulation of the computations of a polynomial-space bounded TM) and then show how to alter this reduction in order to obtain the desired result. Unfortunately, this type of reductions is not very useful for ETH-based lower-bound proofs. However, in an earlier paper, [PERSON] [23] proved that Aperiodicity is CoNP-hard. His reduction is from 3 SAT (on \(n\) variables and \(m\) clauses), and it produces a minimum-state DFA with \(O(nm)\) many states. Hence, we can immediately conclude a lower bound of \(O\left(2^{o(\sqrt{q})}\right)\) for Aperiodicity on \(q\)-state DFAs. This can be improved as follows. The basic idea of the proof of the next proposition is to reduce the intersection problem (in a restricted version) to aperiodicity. Given language \(L_{1},L_{2},\ldots,L_{k}\), consider the language \(L=(L_{1}\$L_{2}\$\ldots\$L_{k}\$)^{*}\), and let \(A\) be its minimal automaton. One direction is easy: if the intersection of the languages \(L_{1},\ldots,L_{k}\) contains a word \(u\), then \((u\$)^{k}\) forms a cycle in \(A\) starting at the initial state, but \(u\$\) does not. This gives the idea to show that if there is a word \(w\) in the intersection, then the language \(L\) is not aperiodic. The other direction is more involved and requires that the languages \(L_{1},\ldots,L_{k}\) are themselves aperiodic, and that \(k\) is a prime. Theorem 4.1: _Assuming ETH, there is no algorithm for solving Aperiodicity for \(q\)-state DFAs on arbitrary input alphabets that runs in time \(O\left(2^{o(q)}\right)\)._  
Proof: We will show this by reducing a restricted version of the intersection problem to Aperiodicity. Proposition 2 is stated only for general automata, but as the hardness part of the proof only uses automata which are aperiodic, the following claim holds:  
Claim 1: _Let \(q\geqslant 3\) be fixed. Let \(L_{1},\ldots,L_{k}\) be star-free languages given by their minimal automata \(A_{1},\ldots,A_{k}\) over some alphabet \(\Sigma\), where the number of states of each \(A_{i}\) is bounded by \(q\).