weakened form of the second condition, the ADFA $\mathcal{A}$ not having a
stronger property than the CEP, already implies the first condition.

######  Lemma A.25.

The following assertion holds:

$\displaystyle\neg(\forall w=\sigma_{1}\dots\sigma_{n}\in L.\exists
i\in\\{0,\dots,n-2\\}.\exists l\in\\{2,\dots,n-i\\}.$ $\displaystyle\hskip
56.9055pt\delta(q_{0},\sigma_{1}\dots\sigma_{i}\sigma_{i+l}\dots\sigma_{n})=q_{n+1})$
$\displaystyle\Rightarrow$
$\displaystyle\neg(\Sigma_{n-1,n}\subseteq\bigcup_{j=0}^{n-1}\Sigma_{j,n+1})$

######  Proof A.26.

We proof the contraposition. Therefore we assume that
$\Sigma_{n-1,n}\subseteq\bigcup_{j=0}^{n-1}\Sigma_{j,n+1}$. Let
$w=\sigma_{1}\dots\sigma_{n}\in\Sigma^{n}$ with
$w\in\mathcal{L}(\mathcal{A})$. We need to show that there are
$i\in\\{0,\dots,n-2\\},l\in\\{2,\dots,n-i\\}$ such that
$\delta(q_{0},\sigma_{1}\dots\sigma_{i}\sigma_{i+l}\dots\sigma_{n})=q_{n+1}$.

Clearly, we have $\sigma_{j}\in\Sigma_{j-1,j}$ for each $j\in\\{1,\dots,n\\}$.
In particular, we have $\sigma_{n}\in\Sigma_{n-1,n}$. Since
$\Sigma_{n-1,n}\subseteq\bigcup_{j=0}^{n-1}\Sigma_{j,n+1}$, there then exists
an $i\in\\{0,\dots,n-1\\}$ with $\sigma_{n}\in\Sigma_{i,n+1}$. It clearly
holds that $i\neq n-1$ and therefore we have $i\in\\{0,\dots,n-2\\}$.

Now we select $l=n-i$. Note that this implies $l=n-i\in\\{2,\dots,n-i\\}$.
Then we have:

$\displaystyle\delta(q_{0},\sigma_{1}\dots\sigma_{i}\sigma_{i+l}\dots\sigma_{n})$
$\displaystyle=$
$\displaystyle\delta(q_{0},\sigma_{1}\dots\sigma_{i}\sigma_{n})$
$\displaystyle=$ $\displaystyle\delta(q_{i},\sigma_{n})$ $\displaystyle=$
$\displaystyle q_{n+1}.$

In conclusion, we have proven the existence of values
$i\in\\{0,\dots,n-2\\},l\in\\{2,\dots,n-i\\}$ such that
$\delta(q_{0},\sigma_{1}\dots\sigma_{i}\sigma_{i+l}\dots\sigma_{n})=q_{n+1}$.
Thus, we have proven the contraposition of the implication and therefore the
implication itself. The proof of Lemma A.25 is complete.

With Lemmas A.23 and A.25 in hand, the proof of 1 (1) is trivial:

######  Proof A.27 (Proof of 1 (1)).

Assume that the safety DFA $\mathcal{A}$ does not have the CEP. With Lemma
A.25 this implies
$\neg(\Sigma_{n-1,n}\subseteq\bigcup_{j=0}^{n-1}\Sigma_{j,n+1})$. Therefore,
both conditions of Lemma A.23 are satisfied and $\mathcal{A}$ is prime. We are
done.

We have proven 1 (1). That is, we have proven the primality of $\mathcal{A}$
if $\mathcal{A}$ is a safety DFA and does not have the CEP.

###  A.5 Concluding remarks

Our goal for Appendix A was to prove Theorem 3.1, thereby completely
characterizing the compositionality of ADFAs and thus of finite languages. To
do so, we set out to prove 1 (1)-(1), which taken together imply Theorem 3.1.

In Sections A.1, A.2, A.3 and A.4 we have proven (1)-(1) one after the other.
Note that while (1) and (1), which cover the cases of non-linear ADFAs and
linear ADFAs with a $\sigma^{n}\in\mathcal{L}(\mathcal{A})$, were fairly
simple to prove, the remaining (1)-(1) covering linear ADFAs with
$\sigma^{n}\notin\mathcal{L}(\mathcal{A})$ for all $\sigma\in\Sigma$ required
a lot more work. The difficulty arose from extensions of words
$w\in\mathcal{L}(\mathcal{A}),|w|=n$.

First, we have seen that if such an ADFA is not a safety DFA then it is
composite. This holds because one of the additional rejecting states can be
used to construct DFAs rejecting the mentioned extensions. These DFAs do not
need a rejecting sink and instead circle back from their last state $q_{n}$ to
an earlier state after reading an appropriate prefix of the extension.

Second, we have seen that if the ADFA has the CEP then it is composite,
regardless of its accepting and rejecting states. This holds because using the
CEP we can construct DFAs rejecting the extensions. They essentially omit one
state of the original ADFA and can thus employ a rejecting sink.

Finally, we have seen that if the ADFA is a safety DFA and does not have the
CEP then the ADFA is prime. This holds because a safety DFA can be decomposed
into safety DFAs. Therefore, the DFAs used in the decomposition have to employ
a rejecting sink and are therefore, intuitively speaking, one state short to
read words of length $n$. Thus, they are necessarily confused about at least
two prefixes of a word of length $n$. With the CEP not holding, we have shown
that this implies primality.

This concludes the proof of Theorem 3.1 and thereby the characterization of
the compositionality of ADFAs and thus of finite languages. This also
completes the proofs for Section 3.

##  Appendix B Proofs for Section 4

We use the characterization of the compositionality of ADFAs to prove: See 4.1

We will start by showing that $\textsc{Prime-DFA}_{\text{fin}}$ is in NL,
before proving the NL-hardness. To prove that $\textsc{Prime-
DFA}_{\text{fin}}$ is in NL, we argue:

######  Lemma B.1.

Algorithm 1 is an NL-algorithm for $\textsc{Prime-DFA}_{\text{fin}}$.

######  Proof B.2.

We begin by arguing that Algorithm 1 indeed decides $\textsc{Prime-
DFA}_{\text{fin}}$. Afterwards, we argue that Algorithm 1 can be implemented
in logarithmic space.

First, note that it can obviously be decided in NL whether a state $q$ is
reachable from a state $p$ in a given DFA. This further implies that it can be
decided in NL whether a state $q$ is reachable in a given DFA and whether a
given DFA recognizes a non-empty language. Second, it can obviously be decided
in NL whether $\mathcal{L}(\mathcal{A}^{q})\neq\mathcal{L}(\mathcal{A}^{p})$
for a given DFA $\mathcal{A}$ and two states $p,q$.

Now note that with the well-known Immerman-Szelepcsényi theorem
$\textsc{NL}=\textsc{co-NL}$ holds [7]. Therefore, it can also be decided in
NL wether a state $q$ is unreachable from a state $p$ in a given DFA, whether
a state $q$ is unreachable in a given DFA, and whether a given DFA recognizes
the empty language. Further, it can be decided in NL whether
$\mathcal{L}(\mathcal{A}^{q})=\mathcal{L}(\mathcal{A}^{p})$ for a given DFA
$\mathcal{A}$ and two states $p,q$.

With these observations in hand, we argue that Algorithm 1 decides
$\textsc{Prime-DFA}_{\text{fin}}$.

Let $\mathcal{A}=(Q,\Sigma,q_{0},\delta,F)$ with $Q=\\{q_{0},\dots,q_{m}\\}$
be a DFA recognizing a finite language $L$. With
$\hat{\mathcal{A}}=(\hat{Q},\Sigma,q_{0},\hat{\delta},\hat{F})$ we denote the
minimal DFA of $\mathcal{A}$. Note that $\hat{\mathcal{A}}$ is an ADFA. With
$\Sigma_{i,j}$ we denote the usual subsets of $\Sigma$ in the ADFA
$\hat{\mathcal{A}}$.

We begin by making a couple of observations about the behavior of the
algorithm.

First, note that the algorithm accepts in line 1 if $L=\emptyset$. Otherwise,
it resumes.

Second, we consider the values $c$ and $n$ calculated in lines 2-18. We argue
that, if the algorithm is not to reject in line 18, then after line 16 the
variable $c$ has to store the number of states of the given DFA $\mathcal{A}$
which can be removed because they are unreachable or can be merged with a
state with a smaller subscript. Thus, we argue that $c$ is the number of the
removable states of $\mathcal{A}$, meaning
$\text{ind}(\mathcal{A})=|\mathcal{A}|-c$. This implies
$n=(m+1)-c-2=|\mathcal{A}|-c-2=\text{ind}(\mathcal{A})-2$. We begin by
inspecting lines 17-18. In line 17 the value $n$ is calculated depending on
the value $c$. In line 18 the algorithm rejects if no word $w\in\Sigma^{n}$
with $w\in L$ exists. Note that the length of the longest word in $L$ is
$\text{ind}(\mathcal{A})-2$ if $\hat{\mathcal{A}}$ is linear and is strictly
smaller than $\text{ind}(\mathcal{A})-2$ otherwise. Therefore, to avoid being
forced to reject in line 18 the algorithm has to achieve
$n\leq\text{ind}(\mathcal{A})-2$. Since in line 17 the algorithm defines
$n=(m+1)-c-2=|\mathcal{A}|-c-2$, to avoid rejection in line 18 it is necessary
that $|\mathcal{A}|-c\leq\text{ind}(\mathcal{A})$. Thus, $c$ has to be at
least the number of removable states of $\mathcal{A}$ to avoid rejection in
line 18. Consider the calculation of $c$ in lines 2-16. Note that $c$ is
incremented in line 5 only if the current state $q_{i}$ is unreachable and in
line 10 only if $q_{i}$ is reachable and a reachable state $q_{j}$ with $j<i$
is found that is equivalent to $q_{i}$. Also, note that $c$ is incremented at
most once for each $q_{i}$. Therefore, $c$ is smaller or equal the number of
removable states of $\mathcal{A}$, meaning
$|\mathcal{A}|-c\geq\text{ind}(\mathcal{A})$, with equality being achieved
only if the algorithm increments $c$ for each removable $q_{i}$. Thus, to
avoid rejection in line 18 the algorithm has to increment $c$ for each
removable $q_{i}$, so that $c$ is exactly the number of removable states of
$\mathcal{A}$. This then implies $n=(m+1)-c-2=\text{ind}(\mathcal{A})-2$.

Third, note that if the algorithm reaches line 18, that is, if
$L\neq\emptyset$, then it rejects in line 18 if there exists no word
$w\in\Sigma^{n}$ with $w\in L$. Otherwise, it resumes. Since we just argued
that $n=\text{ind}(\mathcal{A})-2$, this means that the algorithm rejects if
$\hat{\mathcal{A}}$ is not linear. Otherwise, it resumes.

Fourth, note that if the algorithm reaches line 19, that is, if
$L\neq\emptyset$ and $\hat{\mathcal{A}}$ is linear, then it accepts if there
is a word $\sigma^{n}\in L$. Otherwise, it resumes.

Fifth, note that if the algorithm reaches line 20 then in lines 20-22 it
checks whether $\mathcal{A}$ is a safety DFA. It rejects if $\mathcal{A}$ is
not a safety DFA. Otherwise, it resumes. Note here that in order to check
whether $\mathcal{A}$ is a safety DFA it is sufficient to ensure that for each
reachable state $q_{i}$ it holds that $q_{i}\notin
F\Rightarrow\mathcal{L}(\mathcal{A}^{q_{i}})=\emptyset$, which implies that
each reachable rejecting state can be replaced by a rejecting sink. Further,
note that deciding whether $q_{i}$ is unreachable and whether
$\mathcal{L}(\mathcal{A}^{q_{i}})\neq\emptyset$ can both be done in NL.

We briefly summarize our observations so far. The algorithm terminates before
reaching line 23 iff:

  * •

$L=\emptyset$, in which case it accepts, or

  * •

$L\neq\emptyset$ and $\hat{\mathcal{A}}$ is not linear, in which case it
rejects, or

  * •

$L\neq\emptyset$ and $\hat{\mathcal{A}}$ is linear and there exists a
$\sigma\in\Sigma$ with $\sigma^{n}\in\Sigma$, in which case it accepts, or

  * •

$L\neq\emptyset$ and $\hat{\mathcal{A}}$ is linear and there exists no
$\sigma\in\Sigma$ with $\sigma^{n}\in\Sigma$ and $\mathcal{A}$ is not a safety
DFA, in which case it rejects.

Therefore, line 23 is reached iff the following holds: $L\neq\emptyset$ and
$\hat{\mathcal{A}}$ is linear and there exists no $\sigma\in\Sigma$ with
$\sigma^{n}\in\Sigma$ and $\mathcal{A}$ is a safety DFA. In this case the DFA
$\mathcal{A}$ is prime iff the minimal DFA $\hat{\mathcal{A}}$ does not have
the CEP. We argue that this is checked in lines 23-28. To be more precise, we
argue that the algorithm rejects in line 26 iff $\hat{\mathcal{A}}$ has the
CEP. The somewhat strange fashion in which the condition is checked, with two
separate selections of words in lines 24 and 26, is motivated by the need to
achieve an NL-algorithm. We will inspect this later.

Assume that $\hat{\mathcal{A}}$ does not have the CEP. We show that this
implies that the algorithm does not reject. Note that a word
$w=\sigma_{1}\dots\sigma_{n}$ can be selected in line 24, which witnesses that
$\hat{\mathcal{A}}$ does not have the CEP. This selection can be done anew for
each $x$. Then the same word can be chosen as $w^{\prime}$ in line 26. Again,
this selection can be done anew for each pair $i,l$. With this selection the
state $\delta(q_{0},\sigma_{1}\dots\sigma_{i}\sigma_{i+l}\dots\sigma_{n})$ is
neither a rejecting state equivalent to a rejecting sink nor an accepting
state from which only rejecting states are reachable. Therefore, a word
$v\in\Sigma^{+}$ with
$\delta(q_{0},\sigma_{1}\dots\sigma_{i}\sigma_{i+l}\dots\sigma_{n}v)\in F$ can
be selected in line 26. That is,
$\sigma_{1}\dots\sigma_{i}\sigma_{i+l}\dots\sigma_{n}v\in L$. Thus, the
algorithm does not reject for any combination of values $x$ and $i,l$.

Now assume that the algorithm does not reject in line 26. We show that this
implies that $\hat{\mathcal{A}}$ does not have the CEP. For each
$x\in\\{1,\dots,n\\}$ a word $w_{x}=\sigma_{1,x}\dots\sigma_{n,x}$ can be
chosen in line 24 so that the algorithm does not reject. Define
$w=\sigma_{1,1}\dots\sigma_{n,n}$. We argue that this $w$ breaches the CEP.

Since $w_{x}\in L$ holds for each $x$, we have $\sigma_{x,x}\in\Sigma_{x-1,x}$
for each $x$. This implies $w\in L$.

Now let $i\in\\{0,\dots,n-2\\},l\in\\{2,\dots,n-i\\}$. Let $x=i+l$. Since the
algorithm does not reject in line 26, we have $\sigma_{x,x}\in\Sigma_{i,j}$
for a $j<i+l$. Expressing this more formally, we have: $\forall
x\in\\{1,\dots,n\\},i\in\\{0,\dots,n-2\\},l\in\\{2,\dots,n-i\\}.x=i+l\Rightarrow\exists
j\in\\{1,\dots,n+1\\}.i<j<i+l\wedge\sigma_{x,x}\in\Sigma_{i,j}$. Getting rid
of the variable $x$, this is clearly equivalent to: $\forall
i\in\\{0,\dots,n-2\\},l\in\\{2,\dots,n-i\\}.\exists
j\in\\{1,\dots,n+1\\}.i<j<i+l\wedge\sigma_{i+l,i+l}\in\Sigma_{i,j}$.

Note that with Lemma A.20 this implies that there are no
$i\in\\{0,\dots,n-2\\},l\in\\{2,\dots,n-i\\}$ such that
$\hat{\delta}(q_{0},\sigma_{1,1}\dots\sigma_{i,i}\sigma_{i+l,i+l}\dots\sigma_{n,n})\in\\{q_{n},q_{n+1}\\}$.
Therefore, the word $w$ breaches the CEP.

Thus we have shown that the algorithm rejects in line 26 iff
$\hat{\mathcal{A}}$ has the CEP.

So far, we have made observations about the behavior of the algorithm. Now we
argue how the correctness of the algorithm arises from our observations.

Let $\mathcal{A}$ be prime. Then with Theorem 3.1 we have:

$L=\emptyset$, or

$L\neq\emptyset$ and $\hat{\mathcal{A}}$ is linear and there is a
$\sigma\in\Sigma$ with $\sigma^{n}\in L$, or

$L\neq\emptyset$ and $\hat{\mathcal{A}}$ is linear and there is no
$\sigma\in\Sigma$ with $\sigma^{n}\in L$ and $\mathcal{A}$ is a safety DFA and
$\hat{\mathcal{A}}$ does not have the CEP. If (1) holds then the algorithm
accepts in line 1. If (2) holds then the algorithm does not reject in line 18
and accepts in line 19. If (3) holds then the algorithm does not reject in
lines 18, 21 or 26 and accepts in line 29.

Now let $\mathcal{A}$ be composite. Then with Theorem 3.1 we have:

$L\neq\emptyset$ and $\hat{\mathcal{A}}$ is not linear, or

$L\neq\emptyset$ and $\hat{\mathcal{A}}$ is linear and there is no
$\sigma\in\Sigma$ with $\sigma^{n}\in L$ and $\mathcal{A}$ is not a safety
DFA, or

$L\neq\emptyset$ and $\hat{\mathcal{A}}$ is linear and there is no
$\sigma\in\Sigma$ with $\sigma^{n}\in L$ and $\mathcal{A}$ is a safety DFA and
$\hat{\mathcal{A}}$ has the CEP. If (1) holds then the algorithm does not
accept in line 1 and rejects in line 18. If (2) holds then the algorithm does
not accept in lines 1 or 19 and rejects in line 21. If (3) holds then the
algorithm does not accept in lines 1 or 19 and rejects in line 26.

Therefore, the algorithm indeed decides $\textsc{Prime-DFA}_{\text{fin}}$.

Now we have to argue that the algorithm can be implemented in logarithmic
space.

We have already argued that the conditions in lines 1-17 can be decided in NL.
In line 18 the word $w$ does not have to be stored completely. Instead, the
algorithm can nondeterministically select one letter after the other, holding
only one letter, a counter and the current state in memory. Therefore, line 18
only needs logarithmic space. Since in line 19 the algorithm only needs to
nondeterministically select a letter and store it and can then proceed
analogously to line 18, that is, holding a counter and the current state in
memory, line 19 only needs logarithmic memory as well. Again, we have already
argued that the conditions in lines 20-22 can be decided in NL.

This leaves us with lines 23-29. The algorithm can store the value $x$. It can
then nondeterministically select a word $w\in\Sigma^{n}$ and check $w\in L$
analogously to line 18. While doing so, it can store the letter $\sigma_{x}$.
The algorithm can then store the values $i,l$. It can nondeterministically
select a word $w^{\prime}\in\Sigma^{n}$ with
$\sigma_{i+l}^{\prime}=\sigma_{x}$ and check $w^{\prime}\in L$ analogously to
line 18. While doing so, it can store the state reached after reading the
prefix $\sigma_{1}^{\prime}\dots\sigma_{i}^{\prime}$. It can then start a
second simulation of a run, beginning in state $q_{i}^{\prime}$, once the
suffix $\sigma_{i+l}^{\prime}\dots\sigma_{n}^{\prime}$ is reached. Since all
this can be done with a constant number of counters, the algorithm only needs
logarithmic space here as well.

Thus, the algorithm only needs logarithmic space.

In conclusion, Algorithm 1 nondeterministically decides $\textsc{Prime-
DFA}_{\text{fin}}$ in logarithmic space. Therefore, Algorithm 1 is an NL-
algorithm for $\textsc{Prime-DFA}_{\text{fin}}$. We are done.

We have proven that $\textsc{Prime-DFA}_{\text{fin}}$ is in NL. Next, we prove
that $\textsc{Prime-DFA}_{\text{fin}}$ is NL-hard. In fact, we prove that
$\textsc{2Prime-DFA}_{\text{fin}}$ is NL-hard, where $\textsc{2Prime-
DFA}_{\text{fin}}$ denotes the restriction of $\textsc{Prime-
DFA}_{\text{fin}}$ to DFAs with at most two letters. Formally, we prove:

######  Lemma B.3.

The problem $\textsc{2Prime-DFA}_{\text{fin}}$ is NL-hard.

######  Proof B.4.

We introduce a number of problems, which we will use in the NL-hardness proof.
We do this locally, since we will not use these problems anywhere else.

In Section 2 we have introduced the problem STCON, which is NL-complete [8].
We now introduce a restriction of STCON. With STCONDAG we denote the
restriction of STCON to directed acyclic graphs. With 2STCONDAG we denote the
restriction of STCONDAG to graphs with a maximum outdegree of two.

With Empty-DFA we denote the emptiness problem for DFAs, that is, the problem
of deciding emptiness for the language recognized by a given DFA. It is known
that Empty-DFA is NL-complete [11]. With $\textsc{Empty-DFA}_{\text{fin}}$ we
denote the restriction of Empty-DFA to DFAs recognizing finite languages. With
$\textsc{2Empty-DFA}_{\text{fin}}$ we denote the restriction of
$\textsc{Empty-DFA}_{\text{fin}}$ to DFAs with at most two letters.

First, we will argue that STCONDAG is NL-complete. Clearly, this implies the
NL-completeness of 2STCONDAG. Second, we will argue that $\textsc{2Empty-
DFA}_{\text{fin}}$ is NL-complete as well by L-reducing 2STCONDAG to
$\textsc{2Empty-DFA}_{\text{fin}}$. Third and finally, we will argue that
$\textsc{2Prime-DFA}_{\text{fin}}$ is NL-hard by L-reducing $\textsc{2Empty-
DFA}_{\text{fin}}$ to $\textsc{2Prime-DFA}_{\text{fin}}$.

We begin by considering STCONDAG. Since STCON is NL-complete, the restriction
STCONDAG is in NL as well. We only have to show NL-hardness. We will provide a
sketch of how the NL-hardness proof of STCON can be adapted for STCONDAG.

The general idea of the NL-hardness proof of STCON is to turn the NL-Turing
maschine of the given problem in NL into a graph. The configurations of the
Turing maschine translate to the nodes of the graph. The connections between
configurations translate to the edges of the graph.

Note that we can adapt any given NL-Turing maschine by introducing a
configuration counter, which simply counts the number of calculation steps of
the original NL-Turing maschine. Since the original NL-Turing maschine can
only go through polynomially many configurations before terminating, this
counter can be implemented using logarithmic space. The adapted Turing
maschine therefore is an NL-Turing maschine as well. Thus, we can use this
adapted NL-Turing maschine and translate it into a graph.

Now note that turning this adapted NL-Turing maschine into a graph clearly
results in a directed acyclic graph. This immediately implies the NL-hardness
of STCONDAG.

We have argued that STCONDAG is in NL and is NL-hard. Thus, it is NL-complete.

Since STCONDAG is in NL, the restriction 2STCONDAG is in NL as well.
Additionally, it is easy to L-reduce STCONDAG to 2STCONDAG, which implies the
NL-hardness of 2STCONDAG. Therefore, the restriction 2STCONDAG is NL-complete.

Next, we will argue that $\textsc{2Empty-DFA}_{\text{fin}}$ is NL-complete.
Note that, since Empty-DFA is in NL, the restriction $\textsc{2Empty-
DFA}_{\text{fin}}$ is in NL as well. We only have to show NL-hardness. To do
this, we L-reduce 2STCONDAG to $\textsc{2Empty-DFA}_{\text{fin}}$ in
practically the same manner as STCON is L-reduced to Empty-DFA.

We can turn any given directed acyclic graph into a DFA using the usual
construction, translating nodes to states and edges to transitions. The
starting node translates to the initial state of the DFA. The target node
translates to the only accepting state. Additionally, we can introduce a
rejecting sink and add transitions into this sink for any nodes without
sufficiently many edges.

Note that this construction results in an ADFA with exactly one accepting
state. Therefore, the constructed ADFA recognizes a finite language and it
recognizes a non-empty language iff the target node is reachable from the
starting node in the graph. Additionally, the number of letters of the
constructed DFA is equal to the maximum outdegree in the underlying graph.
Therefore, this construction witnesses the NL-hardness of $\textsc{2Empty-
DFA}_{\text{fin}}$.

We have argued that $\textsc{2Empty-DFA}_{\text{fin}}$ is in NL and is NL-
hard. Thus, it is NL-complete.

After having established the NL-completeness of $\textsc{2Empty-
DFA}_{\text{fin}}$, we can turn to the NL-hardness of $\textsc{2Prime-
DFA}_{\text{fin}}$. We will L-reduce $\textsc{2Empty-DFA}_{\text{fin}}$ to
$\textsc{2Prime-DFA}_{\text{fin}}$, building on the idea used in [12] to prove
the NL-hardness of Prime-DFA, and additionally employing our characterization
of the compositionality of finite languages.

Let $\mathcal{A}=(Q,\Sigma,q_{0},\delta,F)$ be an input DFA for
$\textsc{2Empty-DFA}_{\text{fin}}$. We construct a DFA
$\mathcal{A}^{\prime}=(Q^{\prime},\Sigma^{\prime},q_{0},\delta^{\prime},F^{\prime})$.
We introduce four new states: $Q^{\prime}=Q\cup\\{p_{0},p_{1},p_{2},p_{-}\\}$.
We set $\Sigma^{\prime}=\Sigma$ if $|\Sigma|=2$. Otherwise, we select a
$\Sigma^{\prime}$ with $\Sigma\subseteq\Sigma^{\prime}$ and
$|\Sigma^{\prime}|=2$. W.l.o.g. we assume $\Sigma^{\prime}=\\{a,b\\}$. We
define: $F^{\prime}=F\cup\\{p_{2}\\}$. Finally, we define $\delta^{\prime}$
for each $q\in Q^{\prime},\sigma\in\Sigma$ as follows:

$\displaystyle\delta^{\prime}(q,\sigma)=\begin{cases}p_{-}&\text{ if
$q\in\\{p_{2},p_{-}\\}$}\\\ p_{2}&\text{ if $q=p_{1}$ and $\sigma=b$}\\\
p_{-}&\text{ if $q=p_{1}$ and $\sigma=a$}\\\ p_{1}&\text{ if $q=p_{0}$ and
$\sigma=a$}\\\ p_{-}&\text{ if $q=p_{0}$ and $\sigma=b$}\\\ p_{0}&\text{ if
$q\in F$}\\\ \delta(q,\sigma)&\text{ if $q\notin F$ and $\sigma\in\Sigma$}\\\
p_{-}&\text{ else, thus if $q\notin F$ and $\sigma\notin\Sigma$}\end{cases}.$

Note that the last case of this definition is only relevant if
$\Sigma\subset\Sigma^{\prime}$.

The main idea of the construction is to plug the series of states
$p_{0},p_{1},p_{2},p_{-}$ behind every accepting state of $\mathcal{A}$. That
is, for every original accepting state of $\mathcal{A}$ every transition leads
to $p_{0}$. These transitions are the only transitions into $p_{0}$. Reading
$ab$ when in $p_{0}$ the DFA $\mathcal{A}^{\prime}$ advances over $p_{1}$ to
$p_{2}$. The other transitions exiting $p_{0}$ and $p_{1}$ lead into the
rejecting sink $p_{-}$. From $p_{2}$ every transition leads into the rejecting
sink $p_{-}$. The other transitions of $\mathcal{A}$ are replicated in
$\mathcal{A}^{\prime}$.

Obviously, the DFA $\mathcal{A}^{\prime}$ recognizes a finite language as
well. Indeed, it is easy to see that
$\mathcal{L}(\mathcal{A}^{\prime})=\\{w,w\sigma ab\hskip 5.69054pt|\hskip
5.69054pt\sigma\in\Sigma^{\prime}\wedge w\in X\\}$, where $X$ is the set of
words recognized by $\mathcal{A}$ which have no real prefix which is
recognized by $\mathcal{A}$ as well.

Now we prove that $\mathcal{A}^{\prime}$ is prime iff $\mathcal{A}$ recognizes
the empty language.

First, assume that $\mathcal{A}$ recognizes the empty language. Then
$\mathcal{L}(\mathcal{A}^{\prime})=\\{w,w\sigma ab\hskip 5.69054pt|\hskip
5.69054pt\sigma\in\Sigma^{\prime}\wedge w\in X\\}=\emptyset$ clearly holds.
Thus, $\mathcal{A}^{\prime}$ recognizes the empty language as well. Therefore,
$\mathcal{A}^{\prime}$ is prime.

Second, assume that $\mathcal{A}$ does not recognize the empty language.
Clearly, this implies that $\mathcal{A}^{\prime}$ does not recognize the empty
language either. Further, every longest word in
$\mathcal{L}(\mathcal{A}^{\prime})$ ends on $ab$. Therefore, no longest word
in $\mathcal{L}(\mathcal{A}^{\prime})$ consists of the repetition of the same
letter. And finally, $\mathcal{A}^{\prime}$ is not a safety DFA, since the
rejecting state $p_{0}$ \- and, for good measure, also the rejecting state
$p_{1}$ \- is reachable in $\mathcal{A}^{\prime}$, from which the accepting
state $p_{2}$ is reachable. With Theorem 3.1 this implies the compositionality
of $\mathcal{A}^{\prime}$.

We have shown that $\mathcal{A}^{\prime}$ is prime iff $\mathcal{A}$
recognizes the empty language. Since $\mathcal{A}^{\prime}$ can clearly be
constructed out of $\mathcal{A}$ in logarithmic space, we have established an
L-reduction from the NL-complete problem $\textsc{2Empty-DFA}_{\text{fin}}$ to
$\textsc{2Prime-DFA}_{\text{fin}}$. Thus, we have shown the NL-hardness of
$\textsc{2Prime-DFA}_{\text{fin}}$. The proof of Lemma B.3 is complete.

We have argued that $\textsc{2Prime-DFA}_{\text{fin}}$ is NL-hard. Clearly,
this implies the NL-hardness of $\textsc{Prime-DFA}_{\text{fin}}$ as well.

With Lemmas B.1 and B.3 we have shown that $\textsc{Prime-DFA}_{\text{fin}}$
as well as $\textsc{2Prime-DFA}_{\text{fin}}$ are in NL and are NL-hard. This
immediately implies the NL-completeness of $\textsc{Prime-DFA}_{\text{fin}}$
and $\textsc{2Prime-DFA}_{\text{fin}}$. This proves Theorem 4.1. We are done
with the proofs for Section 4.

##  Appendix C Proofs for Section 5

We finish the proofs for our results concerning finite languages by proving
the theorems in Section 5, in which finite languages are analyzed under
different notions of compositionality.

We begin by proving: See 5.2

######  Proof C.1 (Proof of Theorem 5.2).

Consider a minimal ADFA $\mathcal{A}=(Q,\Sigma,q_{I},\delta,F)$ recognizing a
non-empty language. Let $n\in\mathbb{N}$ be the length of the longest word in
$\mathcal{L}(\mathcal{A})$.

We begin by proving (i).

First, assume that $\mathcal{A}$ is not linear. This implies
$\text{ind}(\mathcal{A})>n+2$. We reuse the DFA $\mathcal{A}_{w}$ introduced
in the proof of 1 (1) and pictured in Figure 3(a), which is the minimal DFA
recognizing the language $\\{w\\}$ for a word $w\in\Sigma^{*}$. Clearly, we
have
$\mathcal{L}(\mathcal{A})=\bigcup_{w\in\mathcal{L}(\mathcal{A})}\mathcal{L}(\mathcal{A}_{w})$.
And since $\text{ind}(\mathcal{A})>n+2\geq|\mathcal{A}_{w}|$ for each
$w\in\mathcal{L}(\mathcal{A})$, this already implies the
$\cup$-compositionality of $\mathcal{A}$.

Second, assume that $\mathcal{A}$ is linear. This implies
$\text{ind}(\mathcal{A})=n+2$. Let $w\in\Sigma^{*}$ be a word with
$w\in\mathcal{L}(\mathcal{A}),|w|=n$. Let
$\mathcal{B}=(S,\Sigma,s_{I},\eta,G)$ be a minimal DFA with
$\mathcal{L}(\mathcal{B})\subseteq\mathcal{L}(\mathcal{A})$ and
$|\mathcal{B}|<\text{ind}(\mathcal{A})$. We prove
$w\notin\mathcal{L}(\mathcal{B})$, which implies the $\cup$-primality of
$\mathcal{A}$.

We begin by showing that $\mathcal{B}$ has to possess a rejecting sink. Let
$u\in\Sigma^{*}$ with $|u|>n$. Then
$uu^{\prime}\notin\mathcal{L}(\mathcal{A})$ holds for each
$u^{\prime}\in\Sigma^{*}$. Since
$\mathcal{L}(\mathcal{B})\subseteq\mathcal{L}(\mathcal{A})$, this implies
$\eta(s_{0},uu^{\prime})=\eta(\eta(s_{0},u),u^{\prime})\notin G$ for each
$u^{\prime}\in\Sigma^{*}$. Since $\mathcal{B}$ is minimal, this implies that
$\eta(s_{0},u)$ is a rejecting sink.

With this result in hand, we prove $w\notin\mathcal{L}(\mathcal{B})$ by
contradiction. Assume $w\in\mathcal{L}(\mathcal{B})$. Note that $\mathcal{B}$
has at most $n+1$ states and that one of these states is a rejecting sink.
Since $w\in\mathcal{L}(\mathcal{B})$, this rejecting sink is not visited by
$\mathcal{B}$ in its initial run on $w$. Therefore, only $n$ different states
are visited in the initial run on $w$, which implies that one state is visited
twice. Clearly, this implies that $\mathcal{B}$ recognizes an infinite
language. This contradicts
$\mathcal{L}(\mathcal{B})\subseteq\mathcal{L}(\mathcal{A})$. Our proof by
contradiction of $w\notin\mathcal{L}(\mathcal{B})$ is done.

We have shown that there exists no DFA with strictly less than
$\text{ind}(\mathcal{A})$ states that recognizes a subset of
$\mathcal{L}(\mathcal{A})$ and which accepts $w$. Therefore, $\mathcal{A}$ is
$\cup$-prime.

We have proven that $\mathcal{A}$ is $\cup$-prime iff $\mathcal{A}$ is linear.
We are done with (i).

Next, we consider (ii).

First, we prove the DNF-compositionality of $\mathcal{A}$ if $\mathcal{A}$ is
not linear or if there exists no $\sigma\in\Sigma$ with
$\sigma^{n}\in\mathcal{L}(\mathcal{A})$.

If $\mathcal{A}$ is not linear then, as we have shown in (i), $\mathcal{A}$ is
$\cup$-composite. This implies that $\mathcal{A}$ is DNF-composite. Therefore,
we only have to consider the case where $\mathcal{A}$ is linear and where no
$\sigma\in\Sigma$ with $\sigma^{n}\in\mathcal{L}(\mathcal{A})$ exists.

Let $w\in\mathcal{L}(\mathcal{A})$.

If $|w|<n$ we have $|\mathcal{A}_{w}|=|w|+2<n+2=\text{ind}(\mathcal{A})$.
Therefore, for each such word we can simply use the DFA $\mathcal{A}_{w}$ in
the $\cup$-decomposition.

If $|w|=n$ then we can utilize the idea outlined in [12, Example 3.2] to build
two DFAs $\mathcal{A}_{w}^{1},\mathcal{A}_{w}^{2}$ with
$\mathcal{L}(\mathcal{A}_{w}^{1})\cap\mathcal{L}(\mathcal{A}_{w}^{2})=\\{w\\}$
and $|\mathcal{A}_{w}^{1}|,|\mathcal{A}_{w}^{2}|<n+2$, since per requirement
there are at least two different letters in $w$.

Let $\mathcal{A}_{w}^{1}$ be the minimal DFA with
$\mathcal{L}(\mathcal{A}_{w}^{1})=\\{w\\}^{*}$. Let $\sigma\in\Sigma$ such
that $|w|_{\sigma}>0$. Let $\mathcal{A}_{w}^{2}$ be the minimal DFA with
$\mathcal{L}(\mathcal{A}_{w}^{2})=\\{u\in\Sigma^{*}\hskip 5.69054pt|\hskip
5.69054pt|u|_{\sigma}=|w|_{\sigma}\\}$. Obviously, we have
$|\mathcal{A}_{w}^{1}|=|w|+1=n+1<n+2=\text{ind}(\mathcal{A})$ and
$|\mathcal{A}_{w}^{2}|=|w|_{\sigma}+2<n+2=\text{ind}(\mathcal{A})$. It is also
clear that
$\mathcal{L}(\mathcal{A}_{w}^{1})\cap\mathcal{L}(\mathcal{A}_{w}^{2})=\\{w\\}$.

Now we can prove DNF-compositionality of $\mathcal{A}$. Define
$L^{\prime}=\\{w\in L\hskip 5.69054pt|\hskip 5.69054pt|w|<n\\}$. Then
$\mathcal{L}(\mathcal{A})=\bigcup_{w\in
L^{\prime}}\mathcal{L}(\mathcal{A}_{w})\cup\bigcup_{w\in\mathcal{L}(\mathcal{A})\setminus
L^{\prime}}(\mathcal{L}(\mathcal{A}_{w}^{1})\cap\mathcal{L}(\mathcal{A}_{w}^{2}))$
obviously holds. This completes the DNF-compositionality proof of
$\mathcal{A}$ if $\mathcal{A}$ is linear and there exists no $\sigma\in\Sigma$
with $\sigma^{n}\in\mathcal{L}(\mathcal{A})$.

In summary, we have shown that $\mathcal{A}$ is DNF-composite if $\mathcal{A}$
is not linear or if there exists no $\sigma\in\Sigma$ with
$\sigma^{n}\in\mathcal{L}(\mathcal{A})$.

Second, we show that $\mathcal{A}$ is DNF-prime if $\mathcal{A}$ is linear and
there exists a $\sigma\in\Sigma$ with $\sigma^{n}\in\mathcal{L}(\mathcal{A})$.

Assume that $\mathcal{A}$ is as required. Let $\sigma\in\Sigma$ with
$\sigma^{n}\in\mathcal{L}(\mathcal{A})$. Let $s\in\mathbb{N}_{\geq 1}$ and
$t_{1},\dots,t_{s}\in\mathbb{N}_{\geq 1}$ such that there exist DFAs
$\mathcal{A}_{1,1},\dots,\mathcal{A}_{1,t_{1}},\dots,\mathcal{A}_{s,1},\dots,\mathcal{A}_{s,t_{s}}$
with
$\mathcal{L}(\mathcal{A})=\bigcup_{i=1}^{s}\bigcap_{j=1}^{t_{i}}\mathcal{L}(\mathcal{A}_{i,j})$.
Then there exists an $i\in\\{1,\dots,s\\}$ with
$\sigma^{n}\in\bigcap_{j=1}^{t_{i}}\mathcal{L}(\mathcal{A}_{i,j})$. Now note
that with Lemma A.2 there is a $j\in\\{1,\dots,t_{i}\\}$ with
$|\mathcal{A}_{i,j}|\geq n+2$, since otherwise we would have
$\sigma^{n+(n+1)!}\in\bigcap_{j=1}^{t_{i}}\mathcal{L}(\mathcal{A}_{i,j})$,
which would be a contradiction to
$\mathcal{L}(\mathcal{A})=\bigcup_{i=1}^{s}\bigcap_{j=1}^{t_{i}}\mathcal{L}(\mathcal{A}_{i,j})$.
Therefore, $\mathcal{A}$ is not $(\text{ind}(\mathcal{A})-1)$-DNF-
decomposable. Thus, $\mathcal{A}$ is DNF-prime.

We have shown that $\mathcal{A}$ is DNF-prime if $\mathcal{A}$ is linear and
there exists a $\sigma\in\Sigma$ with $\sigma^{n}\in\mathcal{L}(\mathcal{A})$.

In conclusion, we have shown that $\mathcal{A}$ is DNF-prime iff $\mathcal{A}$
is linear and there exists a $\sigma\in\Sigma$ with
$\sigma^{n}\in\mathcal{L}(\mathcal{A})$. We are done with (ii).

The proof of Theorem 5.2 is complete.

Finally, we prove the last remaining result of Section 5. See 5.3

######  Proof C.2 (Proof of Theorem 5.3).

We use Theorems 3.1 and 5.2 to construct a DFA recognizing a finite language
that is DNF-composite but $\cap$\- and $\cup$-prime.

$q_{0}$$q_{1}$$q_{2}$$q_{3}$$q_{4}$$a_{1},a_{2}$$a_{3}$$a_{2},a_{3}$$a_{1}$$a_{3}$$a_{1},a_{2}$$\Sigma$$\Sigma$
Figure 7: DFA recognizing a finite language that is DNF-composite, but
$\cap$\- and $\cup$-prime.

Consider the ADFA $\mathcal{A}=(Q,\Sigma,q_{0},\delta,F)$ pictured in Figure
7. Clearly, $\mathcal{A}$ is minimal and recognizes a non-empty language.
Additionally, $\mathcal{A}$ is linear, there exists no $\sigma\in\Sigma$ with
$\sigma^{3}\in\mathcal{L}(\mathcal{A})$, and $\mathcal{A}$ is a safety DFA.
Finally, $\mathcal{A}$ does not have the CEP, which is witnessed by the word
$a_{1}a_{2}a_{3}\in\mathcal{L}(\mathcal{A})$, since
$\delta(q_{0},a_{2}a_{3}),\delta(q_{0},a_{1}a_{3}),\delta(q_{0},a_{3})=q_{2}\notin\\{q_{3},q_{4}\\}$
holds.

Using Theorems 3.1 and 5.2, this immediately implies that $\mathcal{A}$ is
DNF-composite, but $\cap$\- and $\cup$-prime. The same holds for the language
$\mathcal{L}(\mathcal{A})$. We are done.

This ends our discussion of the proofs for Section 5.

##  Appendix D Proofs for Section 6

We provide proofs for the NL-completeness of 2Minimal-DFA formalized in
Theorem 6.1 and for the complexity boundaries of S-Prime-DFA and kS-Prime-DFA
and of Prime-DFA and kPrime-DFA formalized in Theorems 6.3 and 6.4.

We begin by proving: See 6.1

######  Proof D.1 (Proof of Theorem 6.1).

The NL-completeness of Minimal-DFA and its restrictions kMinimal-DFA for
$k\in\mathbb{N}_{\geq 3}$ is folklore. This immediately implies that 2Minimal-
DFA is in NL. Thus, we only have to prove the NL-hardness of 2Minimal-DFA. To
do so, we will L-reduce the NL-complete problem 2STCON to 2Minimal-DFA using
the construction outlined in Figure 2.

Let $(G,s,t)$ be an input for the problem 2STCON. That is, $G=(V,E)$ is a
directed graph with a maximum outdegree of two, and $s,t\in V$ are nodes of
the graph. We construct a DFA $\mathcal{A}$ with at most two letters that is
minimal iff $t$ is reachable from $s$ in $G$.

If $s=t$ then $t$ is trivially reachable from $s$. In this case, we can
construct an arbitrary minimal DFA with at most two letters. For example, we
can construct the minimal DFA for the empty language. This case is done.

From here on, we assume $s\neq t$. Further, w.l.o.g. we assume
$V=\\{0,\dots,n-1\\}$ and $s=0,t=n-1$.

Let $\mathcal{A}^{\prime}=(Q^{\prime},\Sigma,0,\delta^{\prime},F^{\prime})$ be
the DFA constructed out of $(G,s,t)$ in the usual manner. That is, the nodes
are translated to states, so $Q^{\prime}=V^{\prime}$, and the edges are
translated to transitions. Further, the starting node $s=0$ is translated to
the initial state, and the target node $t=n-1$ is translated to the only
accepting state, so $F^{\prime}=\\{n-1\\}$. If any node has not enough
outgoing edges, self-loops are added. We will base the construction of
$\mathcal{A}$ on $\mathcal{A}^{\prime}$.

From here on, we use $0,1$ as the two letters of the alphabet, so
$\Sigma=\\{0,1\\}$.

We are ready to start with the construction of
$\mathcal{A}=(Q,\Sigma,p_{0},\delta,F)$. We introduce the new states
$p_{0},\dots,p_{n-1}$ and $q_{0},\dots,q_{n-1}$ and $q_{0}^{\prime}$. Further,
for each $i\in Q^{\prime}=V=\\{0,\dots,n-1\\}$ we introduce the states
$i_{0}^{\prime},i_{1}^{\prime},i_{0},i_{1}$. We refer to the states
$i,i_{0}^{\prime},i_{1}^{\prime},i_{0},i_{1}$ for $i\in V$ as $v$-states. We
refer to the states $p_{0},\dots,p_{n-1}$ as $p$-states. And we refer to the
states $q_{0},\dots,q_{n-1}$ and $q_{0}^{\prime}$ as $q$-states. We define
$Q_{p}=\\{p_{0},\dots,p_{n-1}\\},Q_{q}=\\{q_{0},\dots,q_{n-1}\\}\cup\\{q_{0}^{\prime}\\},Q_{v}=\\{i,i_{0}^{\prime},i_{1}^{\prime},i_{0},i_{1}\hskip
5.69054pt|\hskip 5.69054pti\in V\\}$. We say that states
$p_{i},q_{i},i,i_{0}^{\prime},i_{1}^{\prime},i_{0},i_{1}$ for an $i\in V$ are
on layer $i$. We set $p_{0}$ as the initial state. Further, we define
$F=\\{n-1\\}$. We do not introduce any additional letters and use the alphabet
$\Sigma=\\{0,1\\}$ for $\mathcal{A}$.

Finally, we define the transition function $\delta$ in the following way:

  * •

For every $i\in V$ and $\sigma\in\Sigma$ define:

$\displaystyle\delta(p_{i},\sigma)=\begin{cases}p_{i+1}&\text{ if $i<n-1$ and
$\sigma=0$}\\\ p_{n-1}&\text{ if $i=n-1$ and $\sigma=0$}\\\ i&\text{ else,
thus if $\sigma=1$}\end{cases}.$

  * •

For every $q\in\\{q_{0},\dots,q_{n-1}\\}\cup\\{q_{0}^{\prime}\\}$ and
$\sigma\in\Sigma$ define:

$\displaystyle\delta(q,\sigma)=\begin{cases}q_{0}^{\prime}&\text{ if $q=q_{0}$
and $\sigma=0$}\\\ 0&\text{ if $q=q_{0}$ and $\sigma=1$}\\\ q_{1}&\text{ if
$q=q_{0}^{\prime}$ and $\sigma=0$}\\\ q_{i+1}&\text{ if $q=q_{i}$ with
$i\in\\{1,\dots,n-2\\}$ and $\sigma=0$}\\\ q_{0}&\text{ if $q=q_{n-1}$ and
$\sigma=0$}\\\ q&\text{ else, thus if $q\neq q_{0}$ and
$\sigma=1$}\end{cases}.$

  * •

For every $i\in V$ and $\sigma\in\Sigma$ define:
$\delta(i,\sigma)=i_{\sigma}^{\prime}$.

  * •

For every $i\in V$ and $j,\sigma\in\Sigma$ define:

$\displaystyle\delta(i_{j}^{\prime},\sigma)$
$\displaystyle=\begin{cases}i_{j}^{\prime}&\text{ if $\sigma=0$}\\\
i_{j}&\text{ else, thus if $\sigma=1$}\end{cases}$
$\displaystyle\delta(i_{j},\sigma)$
$\displaystyle=\begin{cases}\delta^{\prime}(i,\sigma)&\text{ if $\sigma=j$}\\\
q_{i}&\text{ else, thus if $\sigma\neq j$}\end{cases}.$

Figure 2 displays the DFA $\mathcal{A}$.

We need to show that $\mathcal{A}$ is minimal iff $n-1$ is reachable from $0$
in $G$.

First, we consider the case that $n-1$ is reachable from $0$ in $G$. We show
that in this case the DFA $\mathcal{A}$ is minimal.

If $n-1$ is reachable from $0$ in $G$ there obviously exists a word
$w=\sigma_{1}\dots\sigma_{k}\in\Sigma^{k}$ such that
$\delta^{\prime}(0,w)=n-1$, where $k\in\mathbb{N}_{\geq 1}$. Using $w$ we now
construct a word $w_{+}$ with $\delta(0,w)=n-1$, proving that $n-1$ is
reachable from $0$ in $\mathcal{A}$. To do this, for each
$l\in\\{1,\dots,k\\}$ we need to add the word $1\sigma_{l}$ after each letter
$\sigma_{l}$. This word bridges the states $i_{\sigma},i_{\sigma}^{\prime}$.
Thus, we have $w_{+}=\sigma_{1}(1\sigma_{1})\dots\sigma_{k}(1\sigma_{k})$. It
can be easily verified that $\delta(0,w_{+})=n-1$.

The word $w_{+}$ thus witnesses that $n-1$ is reachable from $0$ in
$\mathcal{A}$. From here on, let $w_{+}$ be a word of minimal length with
$\delta(0,w_{+})$. The minimal length of $w_{+}$ clearly implies that in the
run of $\mathcal{A}$ on $w_{+}$ starting in $0$ there are only $v$-states.

We start our minimality proof of $\mathcal{A}$ by arguing that each state of
$\mathcal{A}$ is reachable. This is obvious, since from $p_{0}$ every state
$p_{i}$ with $i\in V$ can be reached by reading $0^{i}$. From $p_{i}$, every
other state located on layer $i$ is reachable. Therefore, every state of
$\mathcal{A}$ is reachable.

We continue our minimality proof of $\mathcal{A}$ by showing that
$\mathcal{A}$ possesses no equivalent states. Let $a,b\in Q$ with $a\neq b$.
We have to prove
$\mathcal{L}(\mathcal{A}^{a})\neq\mathcal{L}(\mathcal{A}^{b})$. To do this, we
use a lengthy case distinction. Note that in this case distinction we will
often trace cases back to different cases. But we will only trace back cases
to already handled cases, thereby avoiding any circular reasoning.

Case 1: $a,b\in Q_{q}$.

By reading the letter $0$ the DFA $\mathcal{A}$ can circle through the
$q$-states. Therefore, there exists a $k\in\\{0,\dots,n\\}$ such that
$\delta(a,0^{k})=q_{0}$ and $b^{\prime}=\delta(b,0^{k})\neq q_{0}$, where
$b^{\prime}\in Q_{q}$. Then we clearly have
$\delta(a,0^{k}1w_{+})=\delta(0,w_{+})=n-1$ and
$\delta(b,0^{k}1w_{+})=\delta(b^{\prime},w_{+})\neq n-1$, since the $q$-states
can only be left into state $0$ and $w_{+}$ is a word of minimal length with
$\delta(0,w_{+})=n-1$.

The word $0^{k}1w_{+}$ witnesses the inequivalence of $a$ and $b$. We are done
with Case 1.

Case 2: $a,b\in Q_{p}$.

Let $i,j\in V,i\neq j$ with $a=p_{i},b=p_{j}$. Then we have
$\delta(p_{i},1(011))=q_{i}$ and $\delta(p_{j},1(011))=q_{j}$.

Case 2 can be traced back to Case 1.

Case 3: $a\in Q_{p}\Leftrightarrow b\notin Q_{p}$.

W.l.o.g. let $a\in Q_{p}$. Let $i\in V$ with $a=p_{i}$. Then
$\delta(a,0^{(n-1)-i})=p_{n-1}$ holds. Let $b^{\prime}=\delta(b,0^{(n-1)-i})$.
If $\delta(b^{\prime},1)\neq n-1$ we are done with Case 1 with witness
$0^{(n-1)-i}1$. Therefore, we assume $\delta(b^{\prime},1)=n-1$.

Since $b\notin Q_{p}$, we have $b^{\prime}\notin Q_{p}$. Since $0=s\neq
t=n-1$, we additionally have $\delta(q_{0},1)=0\neq n-1$. Therefore, we have
$b^{\prime}\neq q_{0}$ and thus $b^{\prime}\notin Q_{q}$. Thus, we have
$b^{\prime}\in Q_{v}$. With $\delta(b^{\prime},1)=n-1$ this implies
$b^{\prime}=j_{1}$ for a $j\in V$ with $\delta^{\prime}(j,1)=n-1$. But then
$\delta(j_{1},01)=\delta(q_{j},1)\in\\{q_{j},0\\}$ holds, while at the same
time we have $\delta(p_{n-1},01)=\delta(p_{n-1},1)=n-1$. Then we are done with
Case 1 with witness $0^{(n-1)-i}01$.

We have shown the inequivalence of $a$ and $b$. We are done with Case 3.

Case 4: $(a\in Q_{q}\wedge b\in Q_{v})\vee(a\in Q_{v}\wedge b\in Q_{q})$.

W.l.o.g. let $a\in Q_{q}$.

Case 4.1: $b\notin\\{i_{1},i_{1}^{\prime}\hskip 5.69054pt|\hskip 5.69054pti\in
V\\}$.

Then there exists an $r\in\\{0,1,2\\}$ with $\delta(b,0^{r})=j_{0}^{\prime}$
for a $j\in V$. Let $a^{\prime}=\delta(a,0^{r})$. Note that $a^{\prime}\in
Q_{q}$.

Then there exists an $s\in\\{0,\dots,n\\}$ such that
$\delta(a^{\prime},0^{s})=q_{0}^{\prime}$. Additionally, we have
$\delta(j_{0}^{\prime},0^{s})=j_{0}^{\prime}$. Then we have
$\delta(q_{0}^{\prime},1)=q_{0}^{\prime}$ and
$\delta(j_{0}^{\prime},1)=q_{j}\neq q_{0}^{\prime}$.

In summary, we have $\delta(a,0^{r}0^{s}1)=q_{0}^{\prime}$ and
$\delta(b,0^{r}0^{s}1)=q_{j}$ for a $j\in V$.

Case 4.1 can be traced back to Case 1.

Case 4.2: $b\in\\{i_{1}\hskip 5.69054pt|\hskip 5.69054pti\in V\\}\wedge
a=q_{0}$.

Then we have $\delta(a,0)=\delta(q_{0},0)=q_{0}^{\prime}$ and
$\delta(b,0)=\delta(i_{1},0)=q_{i}$ for an $i\in V$.

Case 4.2 can be traced back to Case 1.

Case 4.3: $b\in\\{i_{1}\hskip 5.69054pt|\hskip 5.69054pti\in V\\}\wedge a\neq
q_{0}$.

Then we have $\delta(a,1)=a$ and $\delta(b,1)=j$ for a $j\in V$.

Case 4.3 can be traced back to Case 4.1.

Case 4.4: $b\in\\{i_{1}^{\prime}\hskip 5.69054pt|\hskip 5.69054pti\in
V\\}\wedge a\neq q_{0}$.

Then we have $\delta(a,1)=a$ and $\delta(b,1)=i_{1}$ for an $i\in V$.

Case 4.4 can be traced back to Case 4.3.

Case 4.5: $b\in\\{i_{1}^{\prime}\hskip 5.69054pt|\hskip 5.69054pti\in
V\\}\wedge a=q_{0}$.

Then we have $\delta(a,0)=q_{0}^{\prime}$ and $\delta(b,0)=b$.

Case 4.5 can be traced back to Case 4.4.

Case 5: $a,b\in Q_{v}$.

Let $i,j\in V$ with $a\in\\{i,i_{0}^{\prime},i_{0},i_{1}^{\prime},i_{1}\\}$
and $b\in\\{j,j_{0}^{\prime},j_{0},j_{1}^{\prime},j_{1}\\}$.

For any $x\in Q$ we define the $q$-distance $\text{q-dist}(x)$ of $x$ as the
length of the shortest word $w\in\Sigma^{*}$ such that $\delta(x,w)\in Q_{q}$.
For a $k\in V$ the state $k$ then has a $q$-distance of three, states
$k_{0}^{\prime}$ and $k_{1}^{\prime}$ have a $q$-distance of two, and states
$k_{0}$ and $k_{1}$ have a $q$-distance of one.

Case 5.1: $\text{q-dist}(a)\neq\text{q-dist}(b)$.

W.l.o.g. let $\text{q-dist}(a)<\text{q-dist}(b)$. Then there exists a word
$w\in\Sigma^{*}$ such that $\delta(a,w)\in Q_{q}$ and $\delta(b,w)\in Q_{v}$.

Case 5.1 can be traced back to Case 4.

Case 5.2: $\text{q-dist}(a)=\text{q-dist}(b)\wedge
a\in\\{i_{0}^{\prime},i_{0}\\}\wedge b\in\\{j_{1}^{\prime},j_{1}\\}$.

Let $r=\text{q-dist}(a)$. Clearly, we have $r\in\\{1,2\\}$. Additionally, we
have $\delta(a,1^{r-1})=i_{0},\delta(a,1^{r})=q_{i}$ and
$\delta(b,1^{r-1})=j_{1},\delta(b,1^{r})=\delta^{\prime}(j,1)\in V\subseteq
Q_{v}$.

Case 5.2 can be traced back to Case 4.

Case 5.3: $\text{q-dist}(a)=\text{q-dist}(b)\wedge
a\in\\{i_{1}^{\prime},i_{1}\\}\wedge b\in\\{j_{0}^{\prime},j_{0}\\}$.

Case 5.3 is analogous to Case 5.2.

Case 5.4: $\text{q-dist}(a)=\text{q-dist}(b)\wedge
a\in\\{i_{0}^{\prime},i_{0}\\}\wedge b\in\\{j_{0}^{\prime},j_{0}\\}$.

Clearly, this implies $i\neq j$. Let $r=\text{q-dist}(a)$. Then
$\delta(a,1^{r})=q_{i},\delta(b,1^{r})=q_{j}$ holds.

Case 5.4 can be traced back to Case 1.

Case 5.5: $\text{q-dist}(a)=\text{q-dist}(b)\wedge
a\in\\{i_{1}^{\prime},i_{1}\\}\wedge b\in\\{j_{1}^{\prime},j_{1}\\}$.

Case 5.5 is analogous to Case 5.4.

Case 5.6: $\text{q-dist}(a)=\text{q-dist}(b)\wedge a=i\wedge b=j$.

Clearly, this implies $i\neq j$. Then
$\delta(a,011)=q_{i},\delta(b,011)=q_{j}$ holds.

Case 5.6 can be traced back to Case 1.

With Cases 1-5 the states $a$ and $b$ are not equivalent.

In conclusion, every state of $\mathcal{A}$ is reachable and $\mathcal{A}$
does not possess two states that are not identical but equivalent. Therefore,
the DFA $\mathcal{A}$ is minimal.

Thus, we have shown that $\mathcal{A}$ is minimal if $n-1$ is reachable from
$0$ in $G$.

Second, we consider the case that $n-1$ is not reachable from $0$ in $G$. We
show that in this case the DFA $\mathcal{A}$ is not minimal.

If $n-1$ is not reachable from $0$ in $G$ then clearly the state $n-1$ is not
reachable from the state $0$ in $\mathcal{A}$, since the $p$-states cannot be
reentered once they were left and the $q$-states can only be left to state
$0$. Additionally, this means that $n-1$ is unreachable from every $q$-state.
Since $n-1$ is the only accepting state of $\mathcal{A}$, this implies that at
least the state $0$ and the $q$-states can be replaced by a rejecting sink.
Since there are a strictly positive number of $q$-states, the DFA constructed
in this manner is strictly smaller than $\mathcal{A}$ but recognizes the same
language as $\mathcal{A}$. Therefore, $\mathcal{A}$ is not minimal.

We have shown that $\mathcal{A}$ is not minimal if $n-1$ is unreachable from
$0$ in $G$.

In conclusion, we have shown that $\mathcal{A}$ is minimal iff $n-1$ is
reachable from $0$ in $G$. Since $\mathcal{A}$ can clearly be constructed in
logarithmic space, we have specified an L-reduction of 2STCON to 2Minimal-DFA.
Thus, the problem 2Minimal-DFA is NL-hard.

Since 2Minimal-DFA is in NL and is NL-hard, it is NL-complete. We are done.

Next, we prove: See 6.3

######  Proof D.2 (Proof of Theorem 6.3).

Before we turn to the proof, we introduce some notation. Let
$\mid\subseteq\mathbb{Z}\times\mathbb{Z}$ be the usual divisibility relation.
That is, for $a,b\in\mathbb{Z}$ it holds that $a\mid b$ iff there exists a
$k\in\mathbb{Z}$ with $ka=b$.

We begin by arguing that S-Prime-DFA is in ExpSpace. This follows directly
from the proof of [12, Theorem 2.4], which states that Prime-DFA is in
ExpSpace. Note that we can adapt this proof with the minor modification that
we now need to consider every DFA with less states than the given DFA instead
of every DFA with less states than the index of the given DFA. This
modification is necessary, since the notion of S-primality uses the size
instead of the index of the given DFA. The remainder of the proof can remain
unaltered. Thus, it follows trivially from [12, Theorem 2.4] that S-Prime-DFA
is in ExpSpace. This implies that the restrictions kS-Prime-DFA for
$k\in\mathbb{N}_{\geq 2}$ are in ExpSpace as well.

Now we consider the lower complexity boundary. We will show that 2S-Prime-DFA
is NL-hard. This immediately implies the NL-hardness of S-Prime-DFA and kS-
Prime-DFA for $k\in\mathbb{N}_{\geq 2}$.

To establish the NL-hardness of 2S-Prime-DFA, we will L-reduce the NL-complete
problem 2STCON to 2S-Prime-DFA. To do this, we will adapt the construction
used in Theorem 6.1.

Let $(G,s,t)$ with $G=(V,E)$ be an input for 2STCON. We construct a DFA
$\hat{\mathcal{A}}=(\hat{Q},\Sigma,p_{0},\hat{\delta},\hat{F})$ with
$\Sigma=\\{0,1\\}$ that is S-prime iff $t$ is reachable from $s$ in $G$.

If $s=t$ then $t$ is trivially reachable from $s$ in $G$ and we can construct
an arbitrary S-prime DFA with $\Sigma=\\{0,1\\}$, for example the minimal DFA
recognizing the empty language. This case is done.

From here on, we assume $s\neq t$. Analogous to the proof of Theorem 6.1 we
further assume w.l.o.g. $V=\\{0,\dots,n-1\\}$ and $s=0,t=n-1$. Additionally,
let $\mathcal{A}=(Q,\Sigma,p_{0},\delta,F)$ be the DFA constructed out of
$(G,s,t)$ in the proof of Theorem 6.1, which is displayed in Figure 2. We
construct $\hat{\mathcal{A}}$ by modifying $\mathcal{A}$.

We expand the set of states. Let $\underline{Q}=\\{\underline{x}\hskip
5.69054pt|\hskip 5.69054ptx\in Q\setminus\\{p_{0}\\}\\}$. Then we define
$\hat{Q}=Q\cup\underline{Q}\cup\\{z_{+}\\}$. Further, set $p_{0}$ as the
initial state and define $\hat{F}=\\{z_{+}\\}$. We keep $\Sigma$ as the
alphabet. Finally, for every $x\in\hat{Q}$ and $\sigma\in\Sigma$ we define:

$\displaystyle\hat{\delta}(x,\sigma)=\begin{cases}z_{+}&\text{ if
$x=z_{+}$}\\\ z_{+}&\text{ if $x=\underline{n-1}$ and $\sigma=1$}\\\
p_{0}&\text{ if $x\in\underline{Q}\setminus\\{\underline{n-1}\\}$ and
$\sigma=1$}\\\ y&\text{ if $x\in\underline{Q}$ and $\sigma=0$, where $y\in Q$
with $\underline{y}=x$}\\\ \underline{\delta(x,\sigma)}&\text{ else, thus if
$x\in Q$}\end{cases}.$

From here on, we use the following notation: For a word
$w=\sigma_{1}\dots\sigma_{n}\in\Sigma^{n}$ with $n\in\mathbb{N}_{\geq 2}$, it
is $f(w)=\sigma_{1}0\sigma_{2}0\dots\sigma_{n-1}0\sigma_{n}$. For
$\sigma\in\Sigma$, it is $f(\sigma)=\sigma$. For the empty word $\varepsilon$,
it is $f(\varepsilon)=\varepsilon$.

We make a couple of observations about $\hat{\mathcal{A}}$.

First, note that every state of $\hat{\mathcal{A}}$ is reachable. We have
$\hat{\delta}(p_{0},f(0^{i}))=\underline{p_{i}}$ for every $i\in V$. From
$\underline{p_{i}}$ every other state of layer $i$ is reachable. Since in this
way the state $\underline{n-1}$ is reachable, the state $z_{+}$ is reachable
as well. Therefore, every state of $\hat{\mathcal{A}}$ is reachable.

Second, note that $\hat{\mathcal{A}}$ is a co-safety DFA, since $z_{+}$ is the
only accepting state and $z_{+}$ is a sink.

Third, note that every two states in $\hat{Q}\setminus\\{z_{+}\\}$ are
reachable from one another. We have $\hat{\delta}(x,1)=p_{0}$ for every
$x\in\underline{Q}\setminus\\{\underline{n-1}\\}$. We further have
$\hat{\delta}(\underline{n-1},001)=p_{0}$. And finally, we have
$\hat{\delta}(x,0)=\underline{\delta(x,0)}$ for every $x\in Q$. Therefore, the
state $p_{0}$ is reachable from every state in $\hat{Q}\setminus\\{z_{+}\\}$.
Since, as just argued, every state of $\hat{\mathcal{A}}$ is reachable, this
immediately implies that every two states in $\hat{Q}\setminus\\{z_{+}\\}$ are
reachable from one another.

The second and third point imply that, in the terminology of [12], the DFA
$\hat{\mathcal{A}}$ is a simple co-safety DFA. That is, a co-safety DFA that
consists of the accepting sink and a second component in which every two
states are reachable from one another. With [12, Theorem 5.5] this implies
that $\hat{\mathcal{A}}$ is prime. Note that here we refer to the original
notion of primality, not S-primality.

Here, it is important to note that a simple co-safety DFA is S-prime iff it is
minimal. This is easy to see. If a DFA, be it a simple co-safety DFA or not,
is not minimal, then it is not S-prime. Therefore, a non-minimal simple co-
safety DFA is not S-prime. Further, if a DFA is minimal, then it is S-prime
iff it is prime. Since every simple co-safety DFA is prime, this implies that
every minimal simple co-safety DFA is S-prime. Therefore, a simple co-safety
DFA is S-prime iff it is minimal.

Finally, we point out that until the accepting sink is reached, the DFA
$\hat{\mathcal{A}}$ alternates between states in $Q$ and $\underline{Q}$. More
precisely, we have:

$\displaystyle\forall x\in
Q.\forall\sigma\in\Sigma.\hat{\delta}(x,\sigma)=\underline{\delta(x,\sigma)},$

and:

$\displaystyle\forall\underline{x}\in\underline{Q}.\hat{\delta}(\underline{x},0)=x\wedge(\underline{x}\neq\underline{n-1}\Rightarrow\hat{\delta}(\underline{x},1)=p_{0})\wedge(\underline{x}=\underline{n-1}\Rightarrow\hat{\delta}(\underline{x},1)=z_{+}).$

This immediately implies:

$\displaystyle\forall w\in\Sigma^{+}.\forall x\in
Q.\hat{\delta}(x,f(w))=\underline{\delta(x,w)}\wedge\hat{\delta}(x,f(w)0)=\delta(x,w),$

and:

$\displaystyle\forall
w\in\Sigma^{+}.\forall\underline{x}\in\underline{Q}.\hat{\delta}(\underline{x},0f(w))=\underline{\delta(x,w)}\wedge\hat{\delta}(\underline{x},0f(w)0)=\delta(x,w).$

Thus, by adding the letter $0$ after every letter of a word the DFA
$\hat{\mathcal{A}}$ can simulate the behavior of the DFA $\mathcal{A}$.

Additionally, this implies:

$\displaystyle\forall n\in\mathbb{N}_{\geq 1}.\forall
w=\sigma_{1}\dots\sigma_{n}\in\Sigma^{n}.\forall x\in Q.$ $\displaystyle\hskip
56.9055pt\hat{\delta}(x,\sigma_{1}\dots\sigma_{n-1})\neq z_{+}$
$\displaystyle\hskip 99.58464pt\Rightarrow$ $\displaystyle\hskip
56.9055pt(\hskip 8.5359pt(\hat{\delta}(x,\sigma_{1}\dots\sigma_{n})\in
Q\Leftrightarrow(2\mid
n)\wedge(\sigma_{n}=0\vee\hat{\delta}(x,\sigma_{1}\dots\sigma_{n-1})\neq\underline{n-1}))$
$\displaystyle\hskip
56.9055pt\wedge(\hat{\delta}(x,\sigma_{1}\dots\sigma_{n})\in\underline{Q}\Leftrightarrow\neg(2\mid
n))$ $\displaystyle\hskip
56.9055pt\wedge(\hat{\delta}(x,\sigma_{1}\dots\sigma_{n})=z_{+}\Leftrightarrow(2\mid
n)\wedge\sigma_{n}=1\wedge\hat{\delta}(x,\sigma_{1}\dots\sigma_{n-1})=\underline{n-1})).$

Thus, if the run of $\hat{\mathcal{A}}$ on a word $w$ beginning in a state in
$Q$ does not end in $z_{+}$ then it ends in a state in $Q$ if $|w|$ is even.
Otherwise, that is, if $|w|$ is odd, such a run ends in a state in
$\underline{Q}$. Further and in particular, if the run of $\hat{\mathcal{A}}$
on a word $w$ beginning in a state in $Q$ ends in $z_{+}$ then $z_{+}$ is
entered for the first time after reading an even number of letters.

Similar observations can be made for runs beginning in a state in
$\underline{Q}$. In particular, if the run of $\hat{\mathcal{A}}$ on a word
$w$ beginning in a state in $\underline{Q}$ ends in $z_{+}$ then $z_{+}$ is
entered for the first time after reading an odd number of letters.

Now we turn to the actual proof. Again, we have to show that
$\hat{\mathcal{A}}$ is S-prime iff $t$ is reachable from $s$ in $G$. We use
our observation that $\hat{\mathcal{A}}$ is S-prime iff it is minimal.

We begin by assuming that $t$ is reachable from $s$ in $G$. We show that
$\hat{\mathcal{A}}$ is minimal, which implies its S-primality. We already
argued that every state of $\hat{\mathcal{A}}$ is reachable. Therefore, we
only have to prove that $\hat{\mathcal{A}}$ does not possess two states
different from each other that are equivalent.

Let $a,b\in\hat{Q}$ with $a\neq b$. If one of them is the accepting sink
$z_{+}$ then the two states are trivially inequivalent. Therefore, we assume
$a,b\neq z_{+}$.

Case 1: $a,b\in Q$.

Since the state $n-1$ needs to be handled separately, we use a second case
distinction.

Case 1.1: $a\neq n-1\wedge b\neq n-1$.

Since $\mathcal{A}$ is minimal, the states $a$ and $b$, which are in $Q$ and
are therefore states of $\mathcal{A}$ as well, are inequivalent in
$\mathcal{A}$. W.l.o.g. let $w\in\Sigma^{*}$ with $\delta(a,w)=n-1$ and
$\delta(b,w)\neq n-1$. Since $a\neq n-1$, we have $w\neq\varepsilon$. Then
with the above observation we have
$\hat{\delta}(a,f(w))=\underline{\delta(a,w)}=\underline{n-1}$ and
$\hat{\delta}(b,f(w))=\underline{\delta(b,w)}\neq\underline{n-1}$.

Thus, the word $f(w)1$ witnesses the inequivalence of $a$ and $b$. We are done
with Case 1.1.

Case 1.2: $a=n-1\vee b=n-1$.

W.l.o.g. let $a=n-1$. Then $b\in Q$ with $b\neq n-1$. We have
$\delta(n-1,1)=(n-1)_{1}^{\prime}$. Let $b^{\prime}=\delta(b,1)$. Obviously,
we have $b^{\prime}\neq(n-1)_{1}^{\prime}$.

If $b^{\prime}\neq n-1$ then with $\hat{\delta}(n-1,f(1)0)=(n-1)_{1}^{\prime}$
and $\hat{\delta}(b,f(1)0)=b^{\prime}\notin\\{n-1,(n-1)_{1}^{\prime}\\}$ the
Case 1.2 can be traced back to Case 1.1.

If $b^{\prime}=n-1$ then we have
$\delta(n-1,11)=\delta((n-1)_{1}^{\prime},1)=(n-1)_{1}$ and
$\delta(b,11)=\delta(n-1,1)=(n-1)_{1}^{\prime}$ and thus
$\hat{\delta}(n-1,f(11)0)=(n-1)_{1}$ and
$\hat{\delta}(b,f(11)0)=(n-1)_{1}^{\prime}$. Then Case 1.2 can be traced back
to Case 1.1.

In summary, Case 1.2 can be traced back to Case 1.1.

Case 2: $a,b\in\underline{Q}$.

Then there exist $c,d\in Q$ with $\underline{c}=a$ and $\underline{d}=b$.
Since $a\neq b$, we have $c\neq d$. Additionally, we have
$\hat{\delta}(a,0)=c$ and $\hat{\delta}(b,0)=d$.

Case 2 can be traced back to Case 1.

Case 3: $(a\in Q\wedge b\in\underline{Q})\vee(a\in\underline{Q}\wedge b\in
Q)$.

W.l.o.g. let $a\in Q$ and $b\in\underline{Q}$. Note that the accepting sink
$z_{+}$ is reachable from both $a$ and $b$, since, as explained above, the
initial state $p_{0}$ is reachable from both $a$ and $b$ and the accepting
sink is reachable from $p_{0}$. Let $w_{a}\in\Sigma^{*}$ be a word of minimal
length with $\hat{\delta}(a,w_{a})=z_{+}$. Let $w_{b}\in\Sigma^{*}$ be a word
of minimal length with $\hat{\delta}(b,w_{b})=z_{+}$. Note that, as explained
above as well, the word $w_{a}$ is of even length, while the word $w_{b}$ is
of odd length. This implies $|w_{a}|\neq|w_{b}|$ and therefore
$|w_{a}|<|w_{b}|$ or $|w_{a}|>|w_{b}|$.

The shorter one of the words $w_{a},w_{b}$ witnesses the inequivalence of $a$
and $b$. We are done with Case 3.

With Cases 1-3 the two states $a$ and $b$ are not equivalent. Therefore, every
state of $\hat{\mathcal{A}}$ is reachable and $\hat{\mathcal{A}}$ does not
possess two states that are not identical but equivalent. Therefore, the DFA
$\hat{\mathcal{A}}$ is minimal.

As explained above, since $\hat{\mathcal{A}}$ is a simple co-safety DFA, the
minimality of $\hat{\mathcal{A}}$ implies its S-primality. Therefore, we have
shown that $\hat{\mathcal{A}}$ is S-prime if $t$ is reachable from $s$ in $G$.

Next, we assume that $t$ is not reachable from $s$ in $G$. We have to show
that $\hat{\mathcal{A}}$ is not S-prime. To do this, we show that
$\hat{\mathcal{A}}$ is not minimal. Since every non-minimal DFA is trivially
S-composite, showing this is sufficient to prove that $\hat{\mathcal{A}}$ is
not S-prime.

To prove that $\hat{\mathcal{A}}$ is not minimal, we prove that the states
$0,q_{0}\in Q\subseteq\hat{Q}$ are equivalent. That is, we prove: $\forall
w\in\Sigma^{*}.\hat{\delta}(0,w)=z_{+}\Leftrightarrow\hat{\delta}(q_{0},w)=z_{+}$.

Let $w\in\Sigma^{*}$.

First, assume that $\hat{\delta}(0,w)=z_{+}$. We have to prove
$\hat{\delta}(q_{0},w)=z_{+}$. Since $0\neq z_{+}$, we have
$w\neq\varepsilon$. Additionally, since $t=n-1$ is unreachable from $s=0$ in
$G$, the state $n-1$ is unreachable from the state $0$ in $\mathcal{A}$.

We prove that this implies the existence of $u,v\in\Sigma^{*}$ where
$\neg(2\mid|u|)$ and $w=u1v$, that is, that there is a $1$ in $w$ at an even
position. Assume by contradiction that there is a $0$ in $w$ at every even
position. Then there exists a $w^{\prime}\in\Sigma^{*}$ with $f(w^{\prime})=w$
if $|w|$ is odd and $f(w^{\prime})0=w$ if $|w|$ is even.

For $f(w^{\prime})=w$, we arrive at a contradiction with:
$z_{+}=\hat{\delta}(0,w0)=\hat{\delta}(0,f(w^{\prime})0)=\delta(0,w^{\prime})\neq
z_{+}$. For $f(w^{\prime})0=w$, we arrive at a contradiction with:
$z_{+}=\hat{\delta}(0,w)=\hat{\delta}(0,f(w^{\prime})0)=\delta(0,w^{\prime})\neq
z_{+}$.

Thus, we have shown by contradiction the existence of $u,v\in\Sigma^{*}$ where
$\neg(2\mid|u|)$ and $w=u1v$. Let $u$ be the shortest prefix of $w$ for which
this holds. Then we clearly have
$\hat{\delta}(0,u)\in\underline{Q}\setminus\\{\underline{n-1}\\}$ and
$\hat{\delta}(q_{0},u)\in\underline{Q}\setminus\\{\underline{n-1}\\}$.
Otherwise, we would have $\hat{\delta}(0,u)=\underline{n-1}$ or
$\hat{\delta}(q_{0},u)=\underline{n-1}$ with $u$ having letter $0$ at every
even position. With the same argument as above this leads to a contradiction,
since for $u^{\prime}\in\Sigma^{*}$ with $f(u^{\prime})=u$ we would have
$\delta(0,u^{\prime})=n-1$ or $\delta(q_{0},u^{\prime})=n-1$.

With $\hat{\delta}(0,u)\in\underline{Q}\setminus\\{\underline{n-1}\\}$ and
$\hat{\delta}(q_{0},u)\in\underline{Q}\setminus\\{\underline{n-1}\\}$ we have
$\hat{\delta}(0,u1)=p_{0}=\hat{\delta}(q_{0},u1)$ and thus
$\hat{\delta}(q_{0},w)=\hat{\delta}(q_{0},u1v)=\hat{\delta}(0,u1v)=\hat{\delta}(0,w)=z_{+}$.

We have shown that $\hat{\delta}(0,w)=z_{+}$ implies
$\hat{\delta}(q_{0},w)=z_{+}$.

Second, we assume $\hat{\delta}(q_{0},w)=z_{+}$. We have to prove
$\hat{\delta}(0,w)=z_{+}$. Note that this case is symmetrical to the first
cast, since above we did not use any specifics of state $0$ that do not hold
for state $q_{0}$. In particular, we have $q_{0}\neq z_{+}$ and thus
$w\neq\varepsilon$, and the state $n-1$ is unreachable from $q_{0}$ in
$\mathcal{A}$. Since this case is symmetrical to the first case, it follows
that $\hat{\delta}(q_{0},w)=z_{+}$ implies $\hat{\delta}(0,w)=z_{+}$.

Then $\hat{\delta}(0,w)=z_{+}$ holds iff $\hat{\delta}(q_{0},w)=z_{+}$.
Therefore, the states $0$ and $q_{0}$ are equivalent. This implies that
$\hat{\mathcal{A}}$ is not minimal.

As outlined above, the non-minimality of $\hat{\mathcal{A}}$ implies the
S-compositionality of $\hat{\mathcal{A}}$. Therefore, we have shown that
$\hat{\mathcal{A}}$ is not S-prime if $t$ is not reachable from $s$ in $G$.

In total, we have shown that $\hat{\mathcal{A}}$ is S-prime iff $t$ is
reachable from $s$ in $G$. Since $\hat{\mathcal{A}}$ can clearly be
constructed in logarithmic space, we have found an L-reduction from 2STCON to
2S-Prime-DFA, thus proving the NL-hardness of 2S-Prime-DFA. This trivially
implies the NL-hardness of S-Prime-DFA and kS-Prime-DFA for
$k\in\mathbb{N}_{\geq 2}$.

We have shown that S-Prime-DFA and its restrictions kS-Prime-DFA for
$k\in\mathbb{N}_{\geq 2}$ are in ExpSpace and are NL-hard. The proof of
Theorem 6.3 is complete.

Finally, we prove: See 6.4

######  Proof D.3 (Proof of Theorem 6.4).

The problem Prime-DFA is in ExpSpace with [12, Theorem 2.4]. This implies that
the restrictions kPrime-DFA for $k\in\mathbb{N}_{\geq 2}$ are in ExpSpace as
well. Therefore, we only have to concern ourselves with the lower complexity
boundary.

We begin by introducing another problem, which we will use in the L-reduction
to establish the lower boundary. In the proof of Lemma B.3 we introduced the
emptiness problem for DFAs, denoted with Empty-DFA, which is known to be NL-
complete [11]. Now we introduce $\textsc{2Empty-DFA}_{\text{q+}}$, which
denotes the restriction of Empty-DFA to DFAs with at most two letters which
have exactly one accepting state, which is an accepting sink.

First, note that, since Empty-DFA is in NL, the restriction $\textsc{2Empty-
DFA}_{\text{q+}}$ is in NL as well. Further, the standard L-reduction of
2STCON to Empty-DFA employs a DFA with at most two letters and exactly one
accepting state. This state can be made into an accepting sink while
preserving the validity of the reduction. Therefore, the problem 2STCON can be
L-reduced to $\textsc{2Empty-DFA}_{\text{q+}}$, which implies the NL-hardness
of $\textsc{2Empty-DFA}_{\text{q+}}$. Thus, the restriction $\textsc{2Empty-
DFA}_{\text{q+}}$ is NL-complete.

Now we return to the problem Prime-DFA and its restrictions kPrime-DFA for
$k\in\mathbb{N}_{\geq 2}$.

The problem Prime-DFA is NL-hard with [12, Theorem 2.5]. But since the DFA
construction used for the L-reduction of Empty-DFA to Prime-DFA introduces an
additional letter, we cannot use it to prove the NL-hardness of 2Prime-DFA.
Instead, we will give an L-reduction of $\textsc{2Empty-DFA}_{\text{q+}}$ to
2Prime-DFA.

Let $\mathcal{A}=(Q,\Sigma,q_{I},\delta,F)$ be an input for $\textsc{2Empty-
DFA}_{\text{q+}}$. W.l.o.g. let $\Sigma=\\{0,1\\}$ and let $F=\\{q_{+}\\}$.
That is, the state $q_{+}$ is the accepting sink of $\mathcal{A}$, which is
the only accepting state of $\mathcal{A}$.

We will construct a DFA
$\hat{\mathcal{A}}=(\hat{Q},\Sigma,q_{I},\hat{\delta},\hat{F})$ that is prime
iff $\mathcal{A}$ recognizes the empty language.

To do this, let
$\mathcal{A}_{6}^{\prime}=(Q_{6}^{\prime},\Sigma,q_{0}^{\prime},\delta_{6}^{\prime},F_{6}^{\prime})$
be the minimal DFA with
$\mathcal{L}(\mathcal{A}_{6}^{\prime})=\\{w\in\Sigma^{*}\hskip
5.69054pt|\hskip 5.69054pt|w|_{1}\equiv 0\mod 6\\}$. Clearly, Figure 8
pictures the DFA $\mathcal{A}_{6}^{\prime}$ correctly. It is equally clear
that $\mathcal{A}_{6}^{\prime}$ is composite, since
$\mathcal{L}(\mathcal{A}_{6}^{\prime})=\mathcal{L}(\mathcal{A}_{2}^{\prime})\cap\mathcal{L}(\mathcal{A}_{3}^{\prime})$,
where $\mathcal{A}_{2}^{\prime},\mathcal{A}_{3}^{\prime}$ are analogous to
$\mathcal{A}_{6}^{\prime}$ but instead of modulo six they use modulo two and
three, respectively.

$q_{0}^{\prime}$$q_{1}^{\prime}$$q_{2}^{\prime}$$q_{3}^{\prime}$$q_{4}^{\prime}$$q_{5}^{\prime}$$0$$1$$0$$1$$0$$1$$0$$1$$0$$1$$0$$1$
Figure 8: DFA $\mathcal{A}_{6}^{\prime}$ with
$\mathcal{L}(\mathcal{A}_{6}^{\prime})=\\{w\in\Sigma^{*}\hskip
5.69054pt|\hskip 5.69054pt|w|_{1}\equiv 0\mod 6\\}$.

Now we construct the DFA $\hat{\mathcal{A}}$ out of $\mathcal{A}$ using
$\mathcal{A}_{6}^{\prime}$. Define $\hat{Q}=Q\cup Q_{6}^{\prime}$. We retain
$q_{I}$ as the initial state and set $q_{0}^{\prime}$, the only accepting
state of $\mathcal{A}_{6}^{\prime}$, as the only accepting state of
$\hat{\mathcal{A}}$. That is, $\hat{F}=\\{q_{0}^{\prime}\\}$. We keep the
alphabet $\Sigma=\\{0,1\\}$ unaltered. Finally, for each $q\in\hat{Q}$ and
$\sigma\in\Sigma$ we define:

$\displaystyle\hat{\delta}(q,\sigma)=\begin{cases}q_{0}^{\prime}&\text{ if
$q=q_{+}$ and $\sigma=0$}\\\ q_{+}&\text{ if $q=q_{+}$ and $\sigma=1$}\\\
\delta(q,\sigma)&\text{ if $q\in Q\setminus\\{q_{+}\\}$}\\\
\delta^{\prime}(q,\sigma)&\text{ else, thus if $q\in Q^{\prime}$}\end{cases}.$

We need to show that $\hat{\mathcal{A}}$ is prime iff $\mathcal{A}$ recognizes
the empty language.

If $\mathcal{A}$ recognizes the empty language then the accepting sink $q_{+}$
is unreachable in $\mathcal{A}$. Obviously, this implies that $q_{+}$ is
unreachable in $\hat{\mathcal{A}}$ as well. Since $q_{0}^{\prime}$, the only
accepting state in $\hat{\mathcal{A}}$, is only reachable from the initial
state $q_{I}$ via $q_{+}$, this implies that $\hat{\mathcal{A}}$ recognizes
the empty language. Thus, the DFA $\hat{\mathcal{A}}$ is prime. We have shown
that the DFA $\hat{\mathcal{A}}$ is prime if $\mathcal{A}$ recognizes the
empty language. This part of the equivalence is done.

Next, we assume that $\mathcal{A}$ does not recognize the empty language. We
have to show that $\hat{\mathcal{A}}$ is not prime.

We begin by constructing the minimal DFA $\hat{\mathcal{A}}^{!}$ recognizing
$\mathcal{L}(\hat{\mathcal{A}})$. Then we prove that $\hat{\mathcal{A}}^{!}$
is composite, which implies that $\hat{\mathcal{A}}$ is composite as well.

Let $\mathcal{A}^{!}=(Q^{!},\Sigma,q_{I}^{!},\delta^{!},F^{!})$ be the minimal
DFA recognizing $\mathcal{L}(\mathcal{A})$. Obviously, the DFA
$\mathcal{A}^{!}$ has exactly one accepting state, which is an accepting sink.
Let $q_{+}^{!}$ be this accepting sink. Then construct
$\hat{\mathcal{A}}^{!}=(\hat{Q}^{!},\Sigma,q_{I}^{!},\hat{\delta}^{!},\hat{F}^{!})$
out of $\mathcal{A}^{!}$ using $\mathcal{A}_{6}^{\prime}$ analogously to the
construction of $\hat{\mathcal{A}}$ out of $\mathcal{A}$ using
$\mathcal{A}_{6}^{\prime}$. That is, redirect the $0$-self-loop of state
$q_{+}^{!}$ of $\mathcal{A}^{!}$ to state $q_{0}^{\prime}$ of
$\mathcal{A}_{6}^{\prime}$, make $q_{I}^{!}$ the initial state, and make
$q_{0}^{\prime}$ the sole accepting state. Clearly, we have
$\mathcal{L}(\hat{\mathcal{A}}^{!})=\mathcal{L}(\hat{\mathcal{A}})$ and every
state in $\hat{\mathcal{A}}^{!}$ is reachable.

Now we prove that $\hat{\mathcal{A}}^{!}$ is the minimal DFA recognizing
$\mathcal{L}(\hat{\mathcal{A}})$. To do this, we only have to prove the
minimality of $\hat{\mathcal{A}}^{!}$. Let
$\mathcal{B}=(S,\Sigma,s_{I},\eta,G)$ be a DFA with
$\mathcal{L}(\hat{\mathcal{A}}^{!})\subseteq\mathcal{L}(\mathcal{B})$ and
$|\mathcal{B}|<|\hat{\mathcal{A}}^{!}|$. We prove
$\mathcal{L}(\hat{\mathcal{A}}^{!})\subset\mathcal{L}(\mathcal{B})$, which
implies the minimality of $\hat{\mathcal{A}}^{!}$.

Since every state in $\hat{\mathcal{A}}^{!}$ is reachable, there exist
$w,w^{\prime}\in\Sigma^{*}$ with
$\hat{\delta}^{!}(q_{I}^{!},w)\neq\hat{\delta}^{!}(q_{I}^{!},w^{\prime})$ and
$\eta(s_{I},w)=\eta(s_{I},w^{\prime})$. Let
$q=\hat{\delta}^{!}(q_{I}^{!},w),q^{\prime}=\hat{\delta}^{!}(q_{I}^{!},w^{\prime})$.

Case 1: $q,q^{\prime}\in Q^{!}$.

Since $\mathcal{A}^{!}$ is minimal, we have
$\mathcal{L}({\mathcal{A}^{!}}^{q})\neq\mathcal{L}({\mathcal{A}^{!}}^{q^{\prime}})$.
W.l.o.g. let
$\mathcal{L}({\mathcal{A}^{!}}^{q})\not\subseteq\mathcal{L}({\mathcal{A}^{!}}^{q^{\prime}})$
and let
$u\in\mathcal{L}({\mathcal{A}^{!}}^{q})\setminus\mathcal{L}({\mathcal{A}^{!}}^{q^{\prime}})$.
Then we have
$wu\in\mathcal{L}(\mathcal{A}^{!}),w^{\prime}u\notin\mathcal{L}(\mathcal{A}^{!})$
and therefore
$wu0\in\mathcal{L}(\hat{\mathcal{A}}^{!}),w^{\prime}u0\notin\mathcal{L}(\hat{\mathcal{A}}^{!})$.
But we also have
$\eta(s_{I},w^{\prime}u0)=\eta(\eta(s_{I},w^{\prime}),u0)=\eta(\eta(s_{I},w),u0)=\eta(s_{I},wu0)$.
With
$wu0\in\mathcal{L}(\hat{\mathcal{A}}^{!})\subseteq\mathcal{L}(\mathcal{B})$
this implies $w^{\prime}u0\in\mathcal{L}(\mathcal{B})$.

With witness $w^{\prime}u0$ we are done with Case 1.

Case 2: $q,q^{\prime}\in Q_{6}^{\prime}$.

Let $i,j\in\\{0,\dots,5\\},i\neq j$ with
$q=q_{i}^{\prime},q^{\prime}=q_{j}^{\prime}$. Then we have
$\hat{\delta}^{!}(q_{i}^{\prime},1^{6-i})=q_{0}^{\prime}$ and
$\hat{\delta}^{!}(q_{j}^{\prime},1^{6-i})\neq q_{0}^{\prime}$. Therefore, we
have
$w1^{6-i}\in\mathcal{L}(\hat{\mathcal{A}}^{!}),w^{\prime}1^{6-i}\notin\mathcal{L}(\hat{\mathcal{A}}^{!})$.
But we also have
$\eta(s_{I},w^{\prime}1^{6-i})=\eta(\eta(s_{I},w^{\prime}),1^{6-i})=\eta(\eta(s_{I},w),1^{6-i})=\eta(s_{I},w1^{6-i})$.
With
$w1^{6-i}\in\mathcal{L}(\hat{\mathcal{A}}^{!})\subseteq\mathcal{L}(\mathcal{B})$
this implies $w^{\prime}1^{6-i}\in\mathcal{L}(\mathcal{B})$.

With witness $w^{\prime}1^{6-i}$ we are done with Case 2.

Case 3: $q\in Q^{!}\Leftrightarrow q^{\prime}\in Q_{6}^{\prime}$.

W.l.o.g. let $q\in Q_{6}^{\prime},q^{\prime}\in Q^{!}$. Let
$i\in\\{0,\dots,5\\}$ with $q=q_{i}^{\prime}$. Then
$\hat{\delta}^{!}(q_{i}^{\prime},1^{6-i})=q_{0}^{\prime}$ holds. Since the
only transition connecting the states in $Q^{!}$ with the states in
$Q_{6}^{\prime}$ is the $0$-Transition from $q_{+}^{!}$ to $q_{0}^{\prime}$,
we have $\hat{\delta}^{!}(q^{\prime},1^{6-i})\in Q^{!}$. Therefore, we have
$w1^{6-i}\in\mathcal{L}(\hat{\mathcal{A}}^{!}),w^{\prime}1^{6-i}\notin\mathcal{L}(\hat{\mathcal{A}}^{!})$.
But analogously to Case 2 we also have
$w^{\prime}1^{6-i}\in\mathcal{L}(\mathcal{B})$.

With witness $w^{\prime}1^{6-i}$ we are done with Case 3.

With Cases 1-3 we have
$\mathcal{L}(\hat{\mathcal{A}}^{!})\subset\mathcal{L}(\mathcal{B})$, which
implies the minimality of $\hat{\mathcal{A}}^{!}$.

We have shown that $\hat{\mathcal{A}}^{!}$ is the minimal DFA recognizing
$\mathcal{L}(\hat{\mathcal{A}})$. Now we prove the compositionality of
$\hat{\mathcal{A}}^{!}$, which implies the compositionality of
$\hat{\mathcal{A}}$ as well.

The compositionality of $\hat{\mathcal{A}}^{!}$ is easy to see. As outlined
above, the DFA $\mathcal{A}_{6}^{\prime}$ is composite with
$\mathcal{L}(\mathcal{A}_{6}^{\prime})=\mathcal{L}(\mathcal{A}_{2}^{\prime})\cap\mathcal{L}(\mathcal{A}_{3}^{\prime})$.
We can then construct the DFAs $\hat{\mathcal{A}}_{2}^{!}$ and
$\hat{\mathcal{A}}_{3}^{!}$ out of $\mathcal{A}^{!}$ using
$\mathcal{A}_{2}^{\prime}$ and $\mathcal{A}_{3}^{\prime}$ respectively in the
same way we constructed $\hat{\mathcal{A}}^{!}$ out of $\mathcal{A}^{!}$ using
$\mathcal{A}_{6}^{\prime}$. We obviously have
$\mathcal{L}(\hat{\mathcal{A}}^{!})=\mathcal{L}(\hat{\mathcal{A}}_{2}^{!})\cap\mathcal{L}(\hat{\mathcal{A}}_{3}^{!})$
and
$|\hat{\mathcal{A}}_{2}^{!}|=|\mathcal{A}^{!}|+|\mathcal{A}_{2}^{\prime}|=|\mathcal{A}^{!}|+2<|\mathcal{A}^{!}|+6=|\mathcal{A}^{!}|+|\mathcal{A}_{6}^{\prime}|=\text{ind}(\hat{\mathcal{A}}^{!})$
as well as
$|\hat{\mathcal{A}}_{3}^{!}|=|\mathcal{A}^{!}|+|\mathcal{A}_{3}^{\prime}|=|\mathcal{A}^{!}|+3<|\mathcal{A}^{!}|+6=|\mathcal{A}^{!}|+|\mathcal{A}_{6}^{\prime}|=\text{ind}(\hat{\mathcal{A}}^{!})$.
Thus, the DFA $\hat{\mathcal{A}}^{!}$ is composite, which implies the
compositionality of $\hat{\mathcal{A}}$.

We have shown that $\hat{\mathcal{A}}$ is composite if $\mathcal{A}$ does not
recognize the empty language.

In conclusion, we have shown that $\hat{\mathcal{A}}$ is prime iff
$\mathcal{A}$ recognizes the empty language. Since $\hat{\mathcal{A}}$ can
obviously be constructed in logarithmic space, we have found an L-reduction of
$\textsc{2Empty-DFA}_{\text{q+}}$ to 2Prime-DFA. Thus, we have shown the NL-
hardness of 2Prime-DFA. This obviously implies the NL-hardness of Prime-DFA
and its restrictions kPrime-DFA for $k\in\mathbb{N}_{\geq 2}$.

We have shown that Prime-DFA and its restrictions kPrime-DFA for
$k\in\mathbb{N}_{\geq 2}$ are in ExpSpace and are NL-hard. The proof of
Theorem 6.4 is complete.

This ends our discussion of the proofs for Section 6.