Technische Universität Dortmund, Germanydaniel.spenner@tu-
dortmund.dehttps://orcid.org/0009-0001-2784-5914 Daniel Alexander Spenner
[100]Theory of computation Regular languages [100]Theory of computation
Problems, reductions and completeness

###### Acknowledgements.

I want to thank Thomas Schwentick for his advice and encouragement.John Q.
Open and Joan R. Access 2 42nd Conference on Very Important Topics (CVIT 2016)
CVIT 2016 CVIT 2016 December 24–27, 2016 Little Whinging, United Kingdom 42 23

# Decomposing Finite Languages

Daniel Alexander Spenner

###### Abstract

The paper completely characterizes the primality of acyclic DFAs, where a DFA
$\mathcal{A}$ is prime if there do not exist DFAs
$\mathcal{A}_{1},\dots,\mathcal{A}_{t}$ with
$\mathcal{L}(\mathcal{A})=\bigcap_{i=1}^{t}\mathcal{L}(\mathcal{A}_{i})$ such
that each $\mathcal{A}_{i}$ has strictly less states than the minimal DFA
recognizing the same language as $\mathcal{A}$. A regular language is prime if
its minimal DFA is prime. Thus, this result also characterizes the primality
of finite languages.

Further, the NL-completeness of the corresponding decision problem
$\textsc{Prime-DFA}_{\text{fin}}$ is proven. The paper also characterizes the
primality of acyclic DFAs under two different notions of compositionality,
union and union-intersection compositionality.

Additionally, the paper introduces the notion of S-primality, where a DFA
$\mathcal{A}$ is S-prime if there do not exist DFAs
$\mathcal{A}_{1},\dots,\mathcal{A}_{t}$ with
$\mathcal{L}(\mathcal{A})=\bigcap_{i=1}^{t}\mathcal{L}(\mathcal{A}_{i})$ such
that each $\mathcal{A}_{i}$ has strictly less states than $\mathcal{A}$
itself. It is proven that the problem of deciding S-primality for a given DFA
is NL-hard. To do so, the NL-completeness of 2Minimal-DFA, the basic problem
of deciding minimality for a DFA with at most two letters, is proven.

###### keywords:

Deterministic finite automaton (DFA), Regular languages, Finite languages,
Decomposition, Primality, Minimality

###### category:

##  1 Introduction

Under intersection compositionality a deterministic finite automaton (DFA)
$\mathcal{A}$ is composite if there exist DFAs
$\mathcal{A}_{1},\dots,\mathcal{A}_{t}$ with
$\mathcal{L}(\mathcal{A})=\bigcap_{i=1}^{t}\mathcal{L}(\mathcal{A}_{i})$ such
that the size of each $\mathcal{A}_{i}$ is smaller than the index of
$\mathcal{A}$. Otherwise, $\mathcal{A}$ is prime [12]. The index of
$\mathcal{A}$ is the size of the minimal DFA recognizing the same language as
$\mathcal{A}$. Prime-DFA denotes the problem of deciding primality for a given
DFA. $\textsc{Prime-DFA}_{\text{fin}}$ denotes the restriction of Prime-DFA to
DFAs recognizing a finite language.

Compositionality in general is a key concept in both practical and theoretical
computer science [3, 19]. The intersection decomposition of finite automata
can be motivated by LTL model checking as well as automaton identification.
Both will be briefly discussed below.

The notion of intersection compositionality of finite automata was introduced
in [12], while a limitation of this notion was already studied in [5].
Surprisingly, [12] found even the complexity of the basic problem Prime-DFA to
be open. They proved that Prime-DFA is in ExpSpace and is NL-hard. So far,
this doubly exponential gap has not been closed.

Given the difficulties in tackling the general problem, it has proven fruitful
to characterize the intersection compositionality of fragments of the regular
languages [12, 9, 10]. Our study joins this line of research by completely
characterizing the intersection compositionality of acyclic DFAs (ADFA) and
thereby of finite languages. Further, we prove the NL-completeness of
$\textsc{Prime-DFA}_{\text{fin}}$ and characterize the compositionality of
finite languages under two different notions of compositionality suggested in
[12], union and union-intersection compositionality.

Additionally, we present a proof of the NL-completeness of the basic problem
2Minimal-DFA, the problem of deciding minimality for a DFA with at most two
letters. For arbitrary alphabets, the NL-hardness is a folklore result that
seemingly has not been explicitly published but follows from the constructions
in [2], while the NL-hardness of 2Minimal-DFA appears to be new [4]. We use
this result to establish complexity boundaries for S-Prime-DFA, a modification
of Prime-DFA using the size of the given DFA, not its index.

#### Related Work

The notion of intersection compositionality was introduced in [12], where the
aforementioned complexity boundaries were established. They already considered
language fragments, analyzing safety DFAs and permutation DFAs. This line of
research was followed up in [9, 10], which focused on unary DFAs and
permutation DFAs, respectively.

The intersection decomposition of automata can be motivated by LTL model
checking, where the validity of a specification, given as an LTL formula, is
checked for a system. The automata-based approach entails translating the
specification into a finite automaton [20]. Since the LTL model checking
problem is PSpace-complete in the size of the LTL formula [1], it is desirable
to decompose the formula into a conjunction of subformulas. This can also be
understood as decomposing the finite automaton corresponding to the formula.

Another application of intersection decomposition arises in the field of
automaton identification. The basic task here is, given a set of labeled
words, to construct a finite automaton conforming to this set [6]. An
interesting approach is to construct multiple automata instead of one, which
can lead to smaller and more intuitive solutions [13].

An alternative notion of compositionality uses concatenation. Here, a language
$L$ is composite if there exist two non-trivial languages $L_{1},L_{2}$ with
$L=L_{1}L_{2}$. The concatenation primality problem for regular languages is
PSpace-complete [14]. The restriction to finite languages is known to be NP-
hard [18], while the conjectured NP-completeness of this restriction remains
open [17, 15, 21].

#### Contributions

In Section 3 we completely characterize the intersection compositionality of
ADFAs and thereby of finite languages. We expand on this by proving the NL-
completeness of $\textsc{Prime-DFA}_{\text{fin}}$ in Section 4, thus showing
that finite languages are significantly easier to handle under intersection
compositionality than under concatenation compositionality. We characterize
the union and union-intersection compositionality of finite languages in
Section 5, where we also prove the existence of languages that are union-
intersection composite but both union prime and intersection prime.

In Section 6 we introduce the problem S-Prime-DFA, which is analogous to
Prime-DFA but uses the size for the definition of compositionality, not the
index. We prove that S-Prime-DFA is in ExpSpace and is NL-hard. We also prove
these boundaries for 2Prime-DFA and 2S-Prime-DFA, the restrictions of the
respective problems to DFAs with at most two letters. To establish these
boundaries we prove the NL-completeness of 2Minimal-DFA.

Detailed proofs of these results are provided in the appendix.

##  2 Preliminaries

A deterministic finite automaton (DFA) is a $5$-tuple
$\mathcal{A}=(Q,\Sigma,q_{I},\delta,F)$, where $Q$ is a finite set of states,
$\Sigma$ is a finite non-empty alphabet, $q_{I}\in Q$ is an initial state,
$\delta:Q\times\Sigma\rightarrow Q$ is a transition function, and $F\subseteq
Q$ is a set of accepting states. As usual, we extend $\delta$ to words:
$\delta:Q\times\Sigma^{*}\rightarrow Q$ with $\delta(q,\varepsilon)=q$ and
$\delta(q,\sigma_{1}\dots\sigma_{n})=\delta(\delta(q,\sigma_{1}\dots\sigma_{n-1}),\sigma_{n})$.
For $q\in Q$, the DFA $\mathcal{A}^{q}$ is constructed out of $\mathcal{A}$ by
setting $q$ as the initial state, thus
$\mathcal{A}^{q}=(Q,\Sigma,q,\delta,F)$.

The run of $\mathcal{A}$ on a word $w=\sigma_{1}\dots\sigma_{n}$ starting in
state $q$ is the sequence $q_{0},\sigma_{1},q_{1},\dots,\sigma_{n},q_{n}$ with
$q_{0}=q$ and $q_{i}=\delta(q_{i-1},\sigma_{i})$ for each
$i\in\\{1,\dots,n\\}$. The initial run of $\mathcal{A}$ on $w$ is the run of
$\mathcal{A}$ on $w$ starting in $q_{I}$. The run of $\mathcal{A}$ on $w$
starting in $q$ is accepting if $q_{n}\in F$, otherwise it is rejecting. The
DFA $\mathcal{A}$ accepts $w$ if the initial run of $\mathcal{A}$ on $w$ is
accepting. Otherwise, it rejects $w$. The language $\mathcal{L}(\mathcal{A})$
of $\mathcal{A}$ is the set of words accepted by $\mathcal{A}$. We say that
$\mathcal{A}$ recognizes $\mathcal{L}(\mathcal{A})$. A language is regular if
there exists a DFA recognizing it. Since we only consider regular languages,
we use the terms language and regular language interchangeably.

The size $|\mathcal{A}|$ of $\mathcal{A}$ is the number of states in $Q$. The
DFA $\mathcal{A}$ is minimal if
$\mathcal{L}(\mathcal{A})\neq\mathcal{L}(\mathcal{B})$ holds for every DFA
$\mathcal{B}$ with $|\mathcal{B}|<|\mathcal{A}|$. It is well known that for
every regular language $L$ there exists a canonical minimal DFA recognizing
$L$. The index $\text{ind}(L)$ of $L$ is the size of this canonical minimal
DFA. The index of $\mathcal{A}$ is the index of the language recognized by
$\mathcal{A}$, thus
$\text{ind}(\mathcal{A})=\text{ind}(\mathcal{L}(\mathcal{A}))$. Note that
$\mathcal{A}$ is minimal iff $|\mathcal{A}|=\text{ind}(\mathcal{A})$.

We borrow a few terms from graph theory. Let
$q_{0},\sigma_{1},q_{1},\dots,\sigma_{n},q_{n}$ be the run of $\mathcal{A}$ on
$w=\sigma_{1}\dots\sigma_{n}$ starting in $q_{0}$. Then $q_{0},\dots,q_{n}$ is
a path in $\mathcal{A}$ from $q_{0}$ to $q_{n}$. The length of this path is
$n$. Thus, for two states $q,q^{\prime}$ there exists a path from $q$ to
$q^{\prime}$ in $\mathcal{A}$ of length $n$ iff there exists a
$w\in\Sigma^{n}$ with $\delta(q,w)=q^{\prime}$. The state $q^{\prime}$ is
reachable from $q$ if there exists a path from $q$ to $q^{\prime}$. Otherwise,
$q^{\prime}$ is unreachable from $q$. Obviously, if $q^{\prime}$ is reachable
from $q$ then there exists a path from $q$ to $q^{\prime}$ of a length
strictly smaller than $|\mathcal{A}|$. We say that $q^{\prime}$ is reachable
if it is reachable from $q_{I}$. Otherwise, it is unreachable. A cycle in
$\mathcal{A}$ is a path $q_{0},\dots,q_{n}$ in $\mathcal{A}$ where
$q_{0}=q_{n}$ and $n\in\mathbb{N}_{\geq 1}$. The DFA $\mathcal{A}$ is acyclic
(ADFA) if every cycle in $\mathcal{A}$ begins in a rejecting sink. Clearly, a
DFA recognizes a finite language iff its minimal DFA is acyclic.

We call a DFA $\mathcal{A}=(Q,\Sigma,q_{I},\delta,F)$ linear if for every
$q,q^{\prime}\in Q$ with $q\neq q^{\prime}$ either $q^{\prime}$ is reachable
from $q$ or $q$ is reachable from $q^{\prime}$, but not both. Thus, in a
linear DFA reachability induces a linear order over the states. Obviously,
every linear DFA has exactly one sink. Furthermore, a minimal ADFA
$\mathcal{A}$ is linear iff $|\mathcal{A}|=n+2$, where $n$ is the length of
the longest word in $\mathcal{L}(\mathcal{A})$.

Consider a word $w=\sigma_{1}\dots\sigma_{n}\in\Sigma^{n}$. A word $wv$ with
$v\in\Sigma^{+}$ is an extension of $w$. A word
$\sigma_{1}\dots\sigma_{i}\sigma_{i+l}\dots\sigma_{n}$ with
$i\in\\{0,\dots,n-2\\},l\in\\{2,\dots,n-i\\}$ is a compression of $w$. An ADFA
$\mathcal{A}$ has the compression-extension-property (CEP) if for every
$w\in\mathcal{L}(\mathcal{A})$ with $|w|=n$, where $n$ is the length of the
longest word in $\mathcal{L}(\mathcal{A})$, there exists a compression
$w^{\prime}$ of $w$ such that every extension of $w^{\prime}$ is rejected by
$\mathcal{A}$.

We introduce a type of DFA already inspected in [12]. A regular language
$L\subseteq\Sigma^{*}$ is a safety language if $w\notin L$ implies $wy\notin
L$ for every $y\in\Sigma^{*}$. A DFA $\mathcal{A}$ is a safety DFA if
$\mathcal{L}(\mathcal{A})$ is a safety language. A regular language
$L\subseteq\Sigma^{*}$ is a co-safety language if the complement language
$\overline{L}$ of $L$ is a safety language. A DFA $\mathcal{A}$ is a co-safety
DFA if $\mathcal{L}(\mathcal{A})$ is a co-safety language. Clearly, every non-
trivial minimal safety DFA has exactly one rejecting state, and this state is
a sink. Conversely, every non-trivial minimal co-safety DFA has exactly one
accepting state, and this state is a sink.

We introduce the notions intersection compositionality and primality of DFAs
and languages, following the definitions in [12]:

######  Definition .

For $k\in\mathbb{N}_{\geq 1}$, a DFA $\mathcal{A}$ is $k$-decomposable if
there exist DFAs $\mathcal{A}_{1},\dots,\mathcal{A}_{t}$ with
$\mathcal{L}(\mathcal{A})=\bigcap_{i=1}^{t}\mathcal{L}(\mathcal{A}_{i})$ and
$|\mathcal{A}_{i}|\leq k$ for each $i\in\\{1,\dots,t\\}$, where
$t\in\mathbb{N}_{\geq 1}$. We call such DFAs
$\mathcal{A}_{1},\dots,\mathcal{A}_{t}$ a $k$-decomposition of $\mathcal{A}$.
We call $\mathcal{A}$ composite if $\mathcal{A}$ is $k$-decomposable for a
$k<\text{ind}(\mathcal{A})$, that is, if it is
$(\text{ind}(\mathcal{A})-1)$-decomposable. Otherwise, we call $\mathcal{A}$
prime.

We use compositionality or $\cap$-compositionality when referring to
intersection compositionality.

When analyzing the compositionality of a given DFA $\mathcal{A}$, it is
sufficient to consider minimal DFAs $\mathcal{B}$ strictly smaller than the
minimal DFA of $\mathcal{A}$ with
$\mathcal{L}(\mathcal{A})\subseteq\mathcal{L}(\mathcal{B})$. Thus, we define
$\alpha(\mathcal{A})=\\{\mathcal{B}\hskip 5.69054pt|\hskip
5.69054pt\mathcal{B}\text{ is a minimal DFA with
}\text{ind}(\mathcal{B})<\text{ind}(\mathcal{A})\text{ and
}\mathcal{L}(\mathcal{A})\subseteq\mathcal{L}(\mathcal{B})\\}$. Obviously, the
DFA $\mathcal{A}$ is composite iff
$\mathcal{L}(\mathcal{A})=\bigcap_{\mathcal{B}\in\alpha(\mathcal{A})}\mathcal{L}(\mathcal{B})$.
We call a word
$w\in(\bigcap_{\mathcal{B}\in\alpha(\mathcal{A})}\mathcal{L}(\mathcal{B}))\setminus\mathcal{L}(\mathcal{A})$
a primality witness of $\mathcal{A}$. Clearly, the DFA $\mathcal{A}$ is
composite iff $\mathcal{A}$ has no primality witness.

We extend the notions of $k$-decompositions, compositionality, primality and
primality witnesses to regular languages by identifying a regular language
with its minimal DFA.

We denote the problem of deciding primality for a given DFA with Prime-DFA. We
denote the restriction of Prime-DFA to DFAs recognizing a finite languages
with $\textsc{Prime-DFA}_{\text{fin}}$. Prime-DFA is in ExpSpace and is NL-
hard [12].

We denote the connectivity problem in directed graphs, which is NL-complete
[8], with STCON. We denote the restriction of STCON to graphs with a maximum
outdegree of two with 2STCON. Clearly, 2STCON is NL-complete as well. We
denote the problem of deciding minimality for a given DFA with Minimal-DFA.
For $k\in\mathbb{N}_{\geq 2}$, the problem kMinimal-DFA is the restriction of
Minimal-DFA to DFAs with at most $k$ letters. As mentioned in Section 1, the
NL-completeness of kMinimal-DFA for $k\in\mathbb{N}_{\geq 3}$ is folklore,
while the NL-hardness of 2Minimal-DFA appears to be open.

##  3 Compositionality of Finite Languages

We characterize the compositionality of ADFAs and thereby of finite languages
by proving:

######  Theorem 3.1.

Consider a minimal ADFA $\mathcal{A}=(Q,\Sigma,q_{I},\delta,F)$ recognizing a
non-empty language. Then $\mathcal{A}$ is prime iff $\mathcal{A}$ is linear
and:

$\sigma^{n}\in\mathcal{L}(\mathcal{A})$ for some $\sigma\in\Sigma$, where
$n\in\mathbb{N}$ is the length of the longest word in
$\mathcal{L}(\mathcal{A})$, or

$\mathcal{A}$ is a safety DFA and $\mathcal{A}$ does not have the CEP.

To prove Theorem 3.1 we will consider five cases in turn.

First, if the ADFA $\mathcal{A}$ is not linear we essentially have a surplus
of states, allowing us to construct one DFA rejecting overlong words and one
specific DFA for each of the remaining words also rejected by $\mathcal{A}$.
This approach fails with linear ADFAs. Nevertheless, we will come back to the
idea of excluding words longer than a threshold value and tailoring a DFA for
each word shorter than the threshold value which has to be rejected as well.

Second, if $\mathcal{A}$ is linear and $\sigma^{n}\in\mathcal{L}(\mathcal{A})$
holds the DFAs in $\alpha(\mathcal{A})$ do not possess enough states to
differentiate the words $\sigma^{0},\dots,\sigma^{n}$ but have to accept
$\sigma^{n}$, which implies cyclic behavior on the words in $\\{\sigma\\}^{*}$
from which primality follows.

Third, if there is no $\sigma\in\Sigma$ with
$\sigma^{n}\in\mathcal{L}(\mathcal{A})$ and $\mathcal{A}$ is not a safety DFA
we can return to the idea of excluding words longer than a threshold value.
For each of the words left to reject, it is possible to construct a DFA
similar to $\mathcal{A}$ but without the rejecting sink, which circles back to
the rejecting non-sink.

Fourth, if there is no $\sigma\in\Sigma$ with
$\sigma^{n}\in\mathcal{L}(\mathcal{A})$ and $\mathcal{A}$ has the CEP we can
utilize DFAs similar to $\mathcal{A}$ possessing a rejecting sink, since the
CEP allows us to skip over one state.

Fifth and finally, if $\mathcal{A}$ is linear and $\mathcal{A}$ is a safety
DFA and does not have the CEP both of the above approaches fail. There is no
state to circle back to, and for the word breaching the CEP skipping over
states is not possible either, which implies primality.

Formalizing these five cases, we get:

######  Claim 1.

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})$. The following assertions hold:

$\mathcal{A}$ is composite if $\mathcal{A}$ is not linear.

$\mathcal{A}$ is prime if $\mathcal{A}$ is linear and
$\sigma^{n}\in\mathcal{L}(\mathcal{A})$ holds for some $\sigma\in\Sigma$.

$\mathcal{A}$ is composite if there is no $\sigma\in\Sigma$ with
$\sigma^{n}\in\mathcal{L}(\mathcal{A})$ and $\mathcal{A}$ is not a safety DFA.

$\mathcal{A}$ is composite if there is no $\sigma\in\Sigma$ with
$\sigma^{n}\in\mathcal{L}(\mathcal{A})$ and $\mathcal{A}$ has the CEP.

$\mathcal{A}$ is prime if $\mathcal{A}$ is linear and $\mathcal{A}$ is a
safety DFA and $\mathcal{A}$ does not have the CEP.

Formalizing the intuition given above for (1) and (1) is not too complex.
Assertions (1)-(1) prove to be much harder. Thus, we commence by discussing
(1) in Section 3.1 and (1) and (1) in Section 3.2. Henceforth, we consider a
minimal ADFA $\mathcal{A}=(Q,\Sigma,q_{I},\delta,F)$ recognizing the non-empty
language $L$ with $\sigma^{n}\notin L$ for each $\sigma\in\Sigma$, where
$n\in\mathbb{N}$ is the length of the longest word in $L$. W.l.o.g. we assume
$Q=\\{q_{0},\dots,q_{n+1}\\}$ with $q_{j}$ being reachable from $q_{i}$ for
all $i<j$, which implies $q_{I}=q_{0}$ and $q_{n}\in F$ with $q_{n+1}$ being
the rejecting sink. Finally, we define $\Sigma_{i,j}=\\{\sigma\in\Sigma\hskip
5.69054pt|\hskip 5.69054pt\delta(q_{i},\sigma)=q_{j}\\}$.

###  3.1 Linear non-safety ADFAs

We consider 1 (1). Therefore, we assume that $\mathcal{A}$ is not a safety
DFA, which implies $\\{q_{n}\\}\subseteq F\subset Q\setminus\\{q_{n+1}\\}$.
Let $d\in\\{0,\dots,n-1\\}$ with $q_{d}\notin F$.

We show the compositionality of $\mathcal{A}$ by specifying an
$(n+1)$-decomposition of $\mathcal{A}$. First, we construct DFAs rejecting
words not in $L$ that are not extensions of words $u\in L,|u|=n$. Afterwards,
we turn to such extensions, whose handling poses the main difficulty. Here, we
first construct DFAs rejecting such extensions that are longer than a certain
threshold value. For the remaining extensions we employ the idea of circling
back to $q_{d}$.

We begin by considering words not in $L$ which are not extensions of words
$u\in L,|u|=n$. We introduce three DFA types handling these words.

First, let $\mathcal{A}_{0}$ be the DFA constructed out of $\mathcal{A}$ by
removing $q_{n}$, redirecting every transition $q\rightarrow q_{n}$ to
$q_{0}$, and including $q_{0}$ into the acceptance set. Clearly,
$\mathcal{A}_{0}\in\alpha(\mathcal{A})$ and $\mathcal{A}_{0}$ rejects every
$w\notin L$ on which $\mathcal{A}$ enters the rejecting sink prematurely, that
is, without entering $q_{n}$.

Second, let $\hat{\mathcal{A}}_{d}$ be the DFA constructed out of
$\mathcal{A}$ by removing $q_{n+1}$, redirecting every transition
$q_{i}\rightarrow q_{n+1}$ with $i<n$ to $q_{n}$ and every transition
$q_{n}\rightarrow q_{n+1}$ to $q_{d}$. Clearly,
$\hat{\mathcal{A}}_{d}\in\alpha(\mathcal{A})$ and $\hat{\mathcal{A}}_{d}$
rejects every $w\notin L$ on which $\mathcal{A}$ does not enter the rejecting
sink.

Third, we construct DFAs rejecting extensions of words $w\in L,|w|<n$ with
$\delta(q_{0},w)=q_{n}$. Let $I=\\{0,\dots,n\\}$. For each
$m\in\\{1,\dots,n-1\\}$ let $I_{m}=\\{(i_{0},\dots,i_{m})\in I^{m+1}\hskip
5.69054pt|\hskip 5.69054pt0=i_{0}<\dots<i_{m}=n\\}$. For each
$\underline{i}\in I_{m}$ define $\mathcal{A}_{\underline{i}}$ as in Figures
1(a) and 1(b). It is easy to confirm that each $\mathcal{A}_{\underline{i}}$
is in $\alpha(\mathcal{A})$ and rejects extensions of words on which
$\mathcal{A}$ visits the states $q_{i_{0}},\dots,q_{i_{m}}$.

$q_{0}$$q_{i_{1}}$$q_{i_{m-1}}$$q_{n}$$q_{n+1}$$q_{+}$$\Sigma_{0,i_{1}}$$\overline{\Sigma_{0,i_{1}}}$$\overline{\Sigma_{i_{1},i_{2}}}$$\Sigma_{i_{m-1},n}$$\overline{\Sigma_{i_{m-1},n}}$$\Sigma$$\Sigma$$\Sigma$
(a) $\mathcal{A}_{\underline{i}}$ if $m<n-1$.

$q_{0}$$q_{j-1}$$q_{j+1}$$q_{n}$$q_{n+1}$$\overline{\Sigma_{0,1}}$$\Sigma_{j-1,j+1}$$\overline{\Sigma_{j-1,j+1}}$$\overline{\Sigma_{j+1,j+2}}$$\Sigma$$\Sigma$
(b) $\mathcal{A}_{\underline{i}}$ if $m=n-1$, where
$\underline{i}=(0,\dots,j-1,j+1,\dots,n)$.

$q_{0}$$q_{1}$$q_{i-1}$$q_{i}$$q_{n-1}$$q_{n}$$\Sigma$$\Sigma$$\Sigma\setminus\\{\sigma\\}$$\sigma$$\Sigma$$\Sigma$$\Sigma$
(c) $\mathcal{A}_{\sigma,i}$.

Figure 1: DFA $\mathcal{A}_{\underline{i}}$ for $\underline{i}\in I_{m}$ with
$m\in\\{1,\dots,n-1\\}$ and DFA $\mathcal{A}_{\sigma,i}$ for
$\sigma\in\Sigma,i\in\\{1,\dots,n\\}$.

Lemma 3.2 formalizes the results concerning $\mathcal{A}_{0}$,
$\hat{\mathcal{A}}_{d}$ and $\mathcal{A}_{\underline{i}}$:

######  Lemma 3.2.

The following assertions hold:

$\mathcal{A}_{0},\hat{\mathcal{A}}_{d},\mathcal{A}_{\underline{i}}\in\alpha(\mathcal{A})$,
where $\underline{i}\in\bigcup_{m=1}^{n-1}I_{m}$.

Consider a word $w\notin L$, where $w$ is not an extension of a word $u\in
L,|u|=n$. Then
$w\notin\mathcal{L}(\mathcal{A}_{0})\cap\mathcal{L}(\hat{\mathcal{A}}_{d})\cap\bigcap_{m=1}^{n-1}\bigcap_{\underline{i}\in
I_{m}}\mathcal{L}(\mathcal{A}_{\underline{i}})$ holds.

Next, we turn to the extensions of words $u\in L,|u|=n$. We begin by
constructing DFAs that taken together reject every word strictly longer than
$n+(n-2)$. Then we turn to the remaining extensions one by one, of which only
a finite number are left to reject.

Let $\sigma\in\Sigma$. Since $\sigma^{n}\notin L$, there exists a value
$i\in\\{1,\dots,n\\}$ with $\sigma\notin\Sigma_{i-1,i}$. Define
$\mathcal{A}_{\sigma,i}$ as in Figure 1(c). First, note that
$\mathcal{A}_{\sigma,i}\in\alpha(\mathcal{A})$ because a word rejected by
$\mathcal{A}_{\sigma,i}$ is strictly longer $n$ or is of length $n$ with
letter $\sigma$ at position $i$. Next, consider a word
$w=\sigma_{1}\dots\sigma_{m}\in\Sigma^{m}$ such that $\sigma_{j}=\sigma$ for a
$j\in\\{1,\dots,m\\}$ with $j\geq i$ and $m\geq j+(n-i)$. After reading the
prefix $\sigma_{1}\dots\sigma_{j-1}$ the DFA $\mathcal{A}_{\sigma,i}$ is at
least in state $q_{i-1}$. Thus, after reading $\sigma_{1}\dots\sigma_{j}$ it
is at least in state $q_{i}$ and will reject after reading $n-i$ more letters.
Since $m\geq j+(n-i)$, we have $w\notin\mathcal{L}(\mathcal{A}_{\sigma,i})$.
Lemma 3.3 formalizes this result:

######  Lemma 3.3.

Let $\sigma\in\Sigma$ and $i\in\\{1,\dots,n\\}$ with
$\sigma\notin\Sigma_{i-1,i}$. The following assertions hold:

$\mathcal{A}_{\sigma,i}\in\alpha(\mathcal{A})$.

Let $m\in\mathbb{N}$. Let $w\in\sigma_{1}\dots\sigma_{m}\in\Sigma^{m}$ such
that $\sigma_{j}=\sigma$ for a $j\in\\{1,\dots,m\\}$ with $j\geq i$ and $m\geq
j+(n-i)$. Then $w$ is rejected by $\mathcal{A}_{\sigma,i}$.

Now consider a word $w=\sigma_{1}\dots\sigma_{m}\in\Sigma^{m}$ with $m\geq
n+(n-1)$ and $\sigma_{1}\dots\sigma_{n}\in L$. Note that Lemma 3.3 implies
$w\notin\mathcal{L}(\mathcal{A}_{\sigma_{n},i})$ where $i\in\\{1,\dots,n\\}$
with $\sigma_{n}\notin\Sigma_{i-1,i}$. With this limitation of length, we only
need DFAs to reject the extensions of words $u\in L,|u|=n$ with a maximum
length of $n+(n-2)$. Consider such an extension
$w=\sigma_{1}\dots\sigma_{m}\in\Sigma^{m}$. That is, $n+1\leq m\leq n+(n-2)$
and $\sigma_{1}\dots\sigma_{n}\in L$. This implies
$\sigma_{i}\in\Sigma_{i-1,i}$ for each $i\in\\{1,\dots,n\\}$ but provides no
information about the $\sigma_{i}$ with $i\in\\{n+1,\dots,m\\}$. Therefore, we
construct DFAs rejecting every such extension not confirming to a certain
structure. This structure will be key to the further DFA constructions.

For a word $w\in\Sigma^{*}$, let $\mathcal{A}_{w}^{!}$ be the DFA rejecting
exactly the words containing $w$ as a subsequence. Clearly, the following
holds:

######  Lemma 3.4.

Let $w\notin L,|w|=n$. Then $\mathcal{A}_{w}^{!}\in\alpha(\mathcal{A})$ holds.

With the DFAs $\mathcal{A}_{w}^{!}$ for every $w\notin L,|w|=n$ in hand, we
only have to consider extensions of words $u\in L,|u|=n$ with a maximum length
of $n+(n-2)$ for which every subsequence of length $n$ is in $L$.

Let $w=\sigma_{1}\dots\sigma_{m}$ be an extension satisfying these conditions.
We construct a DFA $\tilde{\mathcal{A}}_{w}\in\alpha(\mathcal{A})$ rejecting
$w$. We utilize the rejecting state $q_{d}$ and define
$\tilde{\mathcal{A}}_{w}=(\tilde{Q}_{w},\Sigma,q_{0},\tilde{\delta}_{w},\tilde{F}_{w})$
with $\tilde{Q}=\\{q_{0},\dots,q_{n}\\}$,
$\tilde{F}_{w}=\tilde{Q}_{w}\setminus\\{q_{d}\\}$ and
$\tilde{\delta}_{w}(q_{0},w)=q_{d}$. Further, we have
$\tilde{\delta}_{w}(q_{0},v)=q_{d}$ for a $v\in\Sigma^{*}$ only if
$\delta(q_{0},v)\in\\{q_{d},q_{n+1}\\}$, ensuring
$\tilde{\mathcal{A}}_{w}\in\alpha(\mathcal{A})$. In order to utilize $q_{d}$
in this manner, the DFA $\tilde{\mathcal{A}}_{w}$ simulates the behavior of
$\mathcal{A}$ for the states $q_{0},\dots,q_{d-1}$. The task then is to select
the transitions of states $q_{d},\dots,q_{n}$.

If $|\sigma_{d+1}\dots\sigma_{m}|_{\sigma_{m}}\leq n-d$ the DFA
$\tilde{\mathcal{A}}_{w}$ can simply advance for occurrences of $\sigma_{m}$
and the first $n-d-|\sigma_{d+1}\dots\sigma_{m-1}|_{\sigma_{m}}$ occurrences
of letters unequal to $\sigma_{m}$. Thus, we only have to consider the case
$|\sigma_{d+1}\dots\sigma_{m}|_{\sigma_{m}}>n-d$.

If $\sigma_{n+1}\neq\sigma_{m}$ the DFA $\tilde{\mathcal{A}}_{w}$ can advance
for each letter in $\Sigma$, ensuring
$\tilde{\delta}_{w}(q_{d},\sigma_{d+1}\dots\sigma_{n})=q_{n}$. Further, we can
define $\tilde{\delta}_{w}(q_{n},\sigma_{n+1})=q_{n-[(m-1)-(n+2)+1]}$ and
$\tilde{\delta}_{w}(q_{n},\sigma_{m})=q_{d}$. Note that
$|\sigma_{n+2}\dots\sigma_{m-1}|=(m-1)-(n+2)+1$. Since every subsequence of
$w$ of length $n$ is in $L$, we have
$\tilde{\delta}_{w}(q_{n-[(m-1)-(n+2)+1]},\sigma_{n+2}\dots\sigma_{m-1})=q_{n}$.

The case $\sigma_{n+1}=\sigma_{m}$ is more complex and needs a further case
distinction, but the idea used above of circling back after reading an
appropriate prefix can be employed again.

Lemma 3.5 summarizes these ideas:

######  Lemma 3.5.

Let $w\in\Sigma^{*}$ with $|w|>n$ such that
$w\in\mathcal{L}(\mathcal{A}_{v}^{!})$ for each $v\notin L,|v|=n$ and
$w\in\bigcap_{\sigma\in\Sigma}\mathcal{L}(\mathcal{A}_{\sigma,i_{\sigma}})$,
where for each $\sigma\in\Sigma$ it is
$i_{\sigma}=\max(\\{i\in\\{1,\dots,n\\}\hskip 5.69054pt|\hskip
5.69054pt\sigma\notin\Sigma_{i-1,i}\\})$. Then there exists a DFA
$\tilde{\mathcal{A}}_{w}\in\alpha(\mathcal{A})$ rejecting $w$.

Lemmas 3.2, 3.3, 3.4 and 3.5 imply 1 (1). To be more precise, we have
$\mathcal{L}(\mathcal{A})=\mathcal{L}(\mathcal{A}_{0})\cap\mathcal{L}(\hat{\mathcal{A}}_{d})\cap\bigcap_{m=1}^{n-1}\bigcap_{\underline{i}\in
I_{m}}\mathcal{L}(\mathcal{A}_{\underline{i}})\cap\bigcap_{\sigma\in\Sigma}\mathcal{L}(\mathcal{A}_{\sigma,i_{\sigma}})\cap\bigcap_{w\in
X^{!}}\mathcal{L}(\mathcal{A}_{w}^{!})\cap\bigcap_{w\in\tilde{X}}\mathcal{L}(\tilde{\mathcal{A}}_{w})$,
where $X^{!}=\\{w\in\Sigma^{n}\hskip 5.69054pt|\hskip 5.69054ptw\notin L\\}$
and $\tilde{X}$ is the set of all extensions $w$ of words $u\in L,|u|=n$ with
$|w|\leq n+(n-2)$ for which every subsequence of length $n$ is in $L$. This
proves the compositionality of $\mathcal{A}$ and thereby 1 (1).

###  3.2 Linear safety ADFAs

Next, we consider 1 (1) and (1). For (1) we argue that $\mathcal{A}$ is
composite if it has the CEP, even if $\mathcal{A}$ is a safety DFA, which
makes circling back impossible. For (1) we argue that $\mathcal{A}$ is prime
if it is a safety DFA and it does not have the CEP.

First, we consider (1). We assume that $\mathcal{A}$ has the CEP and argue
that this implies compositionality. Note that we can reuse the DFAs
$\mathcal{A}_{0}$ and $\mathcal{A}_{\underline{i}}$, while
$\hat{\mathcal{A}}_{d}$ is not needed. This again leaves the task of rejecting
the extensions of words $w\in L,|w|=n$. But, since for every such word
$w=\sigma_{1}\dots\sigma_{n}$ there now exist
$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})\in\\{q_{n},q_{n+1}\\}$,
we can construct a DFA $\mathcal{A}_{i,l}\in\alpha(\mathcal{A})$ rejecting
every extension of $w$.

The DFA $\mathcal{A}_{i,l}$ possesses states
$q_{0},\dots,q_{i+l-2},q_{i+l},\dots,q_{n+1}$. It simulates the behavior of
$\mathcal{A}$ for states $q_{0},\dots,q_{i-1}$, redirecting transitions
$q_{j}\rightarrow q_{i+l-1}$ to $q_{i}$. From $q_{i}$ it directly advances to
$q_{i+l}$ if a letter in $\bigcup_{j=i+l}^{n+1}\Sigma_{i,j}$ is read,
otherwise it advances to $q_{i+1}$. The states $q_{i},\dots,q_{i+l-2}$ form a
loop. For states $q_{i+l},\dots,q_{n}$, every transition leads to the direct
successor state. The state $q_{n+1}$ is a rejecting sink.

It is shown in the appendix that every extension of $w$ is rejected by
$\mathcal{A}_{i,l}$, where $i$ is the largest possible value belonging to $w$,
and that $\mathcal{A}_{i,l}\in\alpha(\mathcal{A})$. Thus,
$\mathcal{L}(\mathcal{A})=\mathcal{L}(\mathcal{A}_{0})\cap\bigcap_{m=1}^{n-1}\bigcap_{\underline{i}\in
I_{m}}\mathcal{L}(\mathcal{A}_{\underline{i}})\cap\bigcap_{i=0}^{n-2}\bigcap_{l=2}^{n-i}\mathcal{A}_{i,l}$
holds, proving the compositionality of $\mathcal{A}$ and thus (1).

Next, we consider (1) and assume that $\mathcal{A}$ is a safety DFA and does
not have the CEP. Thus, there is a $w=\sigma_{1}\dots\sigma_{n}$ such that
$\delta(q_{0},\sigma_{1}\dots\sigma_{i}\sigma_{i+l}\dots\sigma_{n})\notin\\{q_{n},q_{n+1}\\}$
holds for every $i\in\\{0,\dots,n-2\\},l\in\\{2,\dots,n-i\\}$. This implies
the existence of a letter $\sigma\in\Sigma_{n-1,n}$ with
$\sigma\notin\Sigma_{j,n+1}$ for every $j\in\\{0,\dots,n-1\\}$. We show in the
appendix that $w\sigma$ is a primality witness of $\mathcal{A}$, thus proving
the primality of $\mathcal{A}$ and thereby (1).

This completes our discussion of 1 (1)-(1). Since they imply Theorem 3.1, we
have characterized the compositionality of ADFAs and thereby of finite
languages.

##  4 Complexity of $\textsc{Prime-DFA}_{\text{fin}}$

After characterizing the compositionality of ADFAs and thereby of finite
languages in Section 3, we now analyze the complexity of $\textsc{Prime-
DFA}_{\text{fin}}$. We argue:

######  Theorem 4.1.

The problem $\textsc{Prime-DFA}_{\text{fin}}$ is NL-complete. The NL-
completeness holds true even when restricting $\textsc{Prime-
DFA}_{\text{fin}}$ to DFAs with at most two letters.

We begin by arguing that $\textsc{Prime-DFA}_{\text{fin}}$ is in NL, providing
an NL-algorithm for $\textsc{Prime-DFA}_{\text{fin}}$ with Algorithm 1. The
algorithm accepts in line 1 if the given DFA $\mathcal{A}$ recognizes the
empty language. Then lines 2-18 ensure that the minimal DFA belonging to
$\mathcal{A}$ is linear. Lines 19-22 ensure that $\mathcal{A}$ is accepted if
a letter $\sigma\in\Sigma$ with $\sigma^{n}\in L$ exists or else that
$\mathcal{A}$ is rejected if it is not a safety DFA. Finally, in lines 23-29
the CEP is checked for $\mathcal{A}$.

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

0: DFA $\mathcal{A}=(Q,\Sigma,q_{0},\delta,F)$ with
$Q=\\{q_{0},\dots,q_{m}\\}$ recognizing a finite language $L$.

0: The DFA $\mathcal{A}$ is prime.

1: Accept if $L=\emptyset$.

2: $c\leftarrow 0$

3: for all $i\in\\{0,\dots,m\\}$ do

4: if $q_{i}$ is unreachable then

5: $c\leftarrow c+1$

6: else

7: $j\leftarrow 0$, $b\leftarrow\textit{true}$

8: while $j\leq i-1$ and $b$ do

9: if $q_{j}$ is reachable and
$\mathcal{L}(\mathcal{A}^{q_{i}})=\mathcal{L}(\mathcal{A}^{q_{j}})$ then

10: $c\leftarrow c+1$

11: $b\leftarrow\textit{false}$

12: end if

13: $j\leftarrow j+1$

14: end while

15: end if

16: end for

17: $n\leftarrow(m+1)-c-2$

18: Choose nondeterministically a word $w\in\Sigma^{n}$. Reject if $w\notin
L$.

19: Choose nondeterministically a letter $\sigma\in\Sigma$. Accept if
$\sigma^{n}\in L$.

20: for all $i\in\\{0,\dots,m\\}$ where $q_{i}$ is not unreachable do

21: Reject if $q_{i}\notin F$ and
$\mathcal{L}(\mathcal{A}^{q_{i}})\neq\emptyset$.

22: end for

23: for all $x\in\\{1,\dots,n\\}$ do

24: Choose nondeterministically a word
$w=\sigma_{1}\dots\sigma_{n}\in\Sigma^{n}$. Reject if $w\notin L$.

25: for all $i\in\\{0,\dots,n-2\\},l\in\\{2,\dots,n-i\\}$ with $i+l=x$ do

26: Choose nondeterministically a word
$w^{\prime}=\sigma_{1}^{\prime}\dots\sigma_{n}^{\prime}\in\Sigma^{n}$ with
$\sigma_{i+l}^{\prime}=\sigma_{x}$ and a word $v\in\Sigma^{+}$. Reject if
$w^{\prime}\notin L$ or if
$\sigma_{1}^{\prime}\dots\sigma_{i}^{\prime}\sigma_{i+l}^{\prime}\dots\sigma_{n}^{\prime}v\notin
L$.

27: end for

28: end for

29: Accept.

The NL-hardness of $\textsc{Prime-DFA}_{\text{fin}}$ can be proven by
L-reducing STCONDAG to $\textsc{Prime-DFA}_{\text{fin}}$, where STCONDAG is
the restriction of STCON to acyclic graphs. The L-reduction is similar to the
L-reduction of STCON to the emptiness problem for DFAs.

##  5 Finite Languages under Different Notions of Compositionality

So far, we have only considered $\cap$-compositionality. Now we will define
two further notions of compositionality and characterize the compositionality
of finite languages for these notions.

######  Definition 5.1.

For $k\in\mathbb{N}_{\geq 1}$, a DFA $\mathcal{A}$ is $k$-$\cup$-decomposable
($k$-DNF-decomposable) if there exist DFAs
$\mathcal{A}_{1},\dots,\mathcal{A}_{t}$
($\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}^{t}\mathcal{L}(\mathcal{A}_{i})$
($\mathcal{L}(\mathcal{A})=\bigcup_{i=1}^{s}\bigcap_{j=1}^{t_{i}}\mathcal{L}(\mathcal{A}_{i,j})$)
and $|\mathcal{A}_{i}|<k$ for every $i$ ($|\mathcal{A}_{i,j}|<k$ for every
pair $i,j$). The further concepts introduced in Section 2 are defined
analogously.

In [12], it is correctly remarked that many results for
$\cap$-compositionality can be trivially transferred to
$\cup$-compositionality. For example, the complexity boundaries for Prime-DFA
established in [12] also hold for $\cup$-compositionality. This does not hold
true for results concerning language fragments that are not closed under
complement. In particular, the complement language of a finite language is not
finite, but co-finite. Thus, characterizing the $\cup$-compositionality of
finite languages is equivalent to characterizing $\cap$-compositionality of
co-finite languages.

Also in [12], the notion of compositionality allowing both union and
intersection is suggested. Note that DNF-compositionality enforces a structure
similar to a disjunctive normal from, but is as strong as unrestricted union-
intersection compositionality. It is correctly remarked in [12] that union-
intersection compositionality - and thus, DNF-compositionality - is strictly
stronger than $\cap$-compositionality. Obviously, it is also strictly stronger
than $\cup$-compositionality. It is less obvious whether languages exist that
are DNF-composite, but are neither $\cap$\- nor $\cup$-composite. We will see
that there are finite languages witnessing this.

The following result characterizes the $\cup$\- and DNF-compositionality of
finite languages:

######  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})$. The following assertions hold:

$\mathcal{A}$ is $\cup$-prime iff $\mathcal{A}$ is linear.

$\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})$.

These conditions are similar to the conditions in Theorem 3.1, but much
simpler. Let $\mathcal{A}$ and $n$ be as required. It is easy to show $\cup$\-
and DNF-compositionality if $\mathcal{A}$ is not linear.

The proof of $\cup$-primality if $\mathcal{A}$ is linear relies on the
observation that every minimal DFA $\mathcal{B}$ with
$\mathcal{L}(\mathcal{B})\subseteq\mathcal{L}(\mathcal{A})$ and
$\text{ind}(\mathcal{B})<\text{ind}(\mathcal{A})$ has to have a rejecting
sink. From this follows that no such DFA $\mathcal{B}$ can accept a word
$w\in\mathcal{L}(\mathcal{A}),|w|=n$. Thus, $\mathcal{A}$ is $\cup$-prime.

If $\mathcal{A}$ is linear and there exists no $\sigma\in\Sigma$ with
$\sigma^{n}\in\mathcal{L}(\mathcal{A})$ the DNF-compositionality of
$\mathcal{A}$ follows from [12, Example 3.2]. On the other hand, if
$\mathcal{A}$ is linear and there exists a $\sigma\in\Sigma$ with
$\sigma^{n}\in\mathcal{L}(\mathcal{A})$ DNF-primality can be shown by adapting
the proof of 1 (1).

As mentioned, Theorems 3.1 and 5.2 immediately imply:

######  Theorem 5.3.

There exists a finite language that is DNF-composite but $\cap$\- and
$\cup$-prime.

To summarize, Theorems 3.1 and 5.2 characterize the $\cap$-, $\cup$\- and DNF-
compositionality of ADFAs and thus of finite languages. Obviously, this
characterizes the $\cap$-, $\cup$\- and DNF-compositionality of co-finite
languages as well. The results further imply the existence of languages that
are DNF-composite but $\cap$\- and $\cup$-prime.

##  6 2Minimal-DFA and S-Prime-DFA

We defined compositionality using the index of the given DFA. Thus, the
compositionality of a DFA $\mathcal{A}$ is a characteristic of
$\mathcal{L}(\mathcal{A})$. Slightly changing the definition, using the size
instead of the index, turns compositionality of $\mathcal{A}$ into a
characteristic of $\mathcal{A}$ itself. It is interesting to analyze the
effects of this change, which results in the notion of S-compositionality.

Many results known for compositionality hold for S-compositionality as well.
The characterization of finite languages in Section 3 and other results
concerning language fragments [12, 9, 10] are valid with only minor technical
modifications. In fact, [9, 10] already implicitly used S-compositionality
instead of compositionality without discussing the differences. The upper
complexity boundary of Prime-DFA holds for S-Prime-DFA as well. But the known
lower boundary, the NL-hardness of Prime-DFA, cannot simply be adapted for
S-Prime-DFA. The lower boundary for S-Prime-DFA is connected to Minimal-DFA,
since non-minimal DFAs are trivially S-composite. Note that Prime-DFA is
connected to the emptiness problem for DFAs in a similar manner [12].

We begin by discussing Minimal-DFA, proving the NL-hardness of 2Minimal-DFA.
Then we formally introduce S-compositionality and prove the NL-hardness of the
restriction 2S-Prime-DFA and thereby of S-Prime-DFA as well. We also prove the
NL-hardness of the restriction 2Prime-DFA, so far only known for the
unrestricted problem Prime-DFA.

###  6.1 NL-hardness of 2Minimal-DFA

As mentioned, the NL-hardness and thus NL-completeness of kMinimal-DFA for
$k\in\mathbb{N}_{\geq 3}$ is folklore, while the NL-hardness of 2Minimal-DFA
appears to be open. We prove:

######  Theorem 6.1.

The problem 2Minimal-DFA is NL-hard and thus NL-complete.

The NL-hardness of 3Minimal-DFA can be proven by L-reducing 2STCON to
3Minimal-DFA. This known reduction uses an additional letter and cannot be
used to prove the NL-hardness of 2Minimal-DFA. We give an L-reduction of
2STCON not using an additional letter, proving the NL-hardness and thus the
NL-completeness of 2Minimal-DFA.

Let $(G,s,t)$ be an input for 2STCON. That is, $G=(V,E)$ is a graph with a
maximum outdegree of two and $s,t\in V$ are nodes of $G$. We construct a DFA
$\mathcal{A}=(Q,\Sigma,q_{I},\delta,F)$ with $\Sigma=\\{0,1\\}$, which is
minimal iff there exists a path in $G$ from $s$ to $t$. If $s=t$ such a path
exists trivially and we can construct the minimal DFA for the empty language.
Thus, we only have to consider the case $s\neq t$. 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$ in the usual manner, that is, by turning nodes
into states, edges into transitions, setting the state $0$ as the initial
state and $n-1$ as the only accepting state. For $\mathcal{A}$, we introduce
the new states $p_{0},\dots,p_{n-1}$, called $p$-states, the new states
$q_{0},\dots,q_{n-1}$ and $q_{0}^{\prime}$, called $q$-states, and for each
$i\in Q^{\prime}$ the states $i_{0}^{\prime},i_{1}^{\prime},i_{0},i_{1}$. We
call the states $i,i_{0}^{\prime},i_{1}^{\prime},i_{0},i_{1}$ for $i\in
Q^{\prime}$ $v$-states. We say that states
$p_{i},q_{i},i,i_{0}^{\prime},i_{1}^{\prime},i_{0},i_{1}$ for an $i\in
Q^{\prime}$ are located on the same layer. Figure 2 specifies the DFA
$\mathcal{A}$ constructed for the L-reduction. We now discuss the key ideas of
this construction.

$p_{0}$$0_{1}^{\prime}$$0$$0_{0}^{\prime}$$q_{0}$$q_{0}^{\prime}$$0_{0}$$0_{1}$$p_{1}$$1_{1}^{\prime}$$1$$1_{0}^{\prime}$$q_{1}$$1_{0}$$1_{1}$$p_{n-1}$${n-1}_{1}^{\prime}$$n-1$${n-1}_{0}^{\prime}$$q_{n-1}$${n-1}_{0}$${n-1}_{1}$$0$$0$$0$$1$$1$$1$$0$$0$$0$$0$$1$$1$$1$$1$$0$$1$$0$$0$$1$$1$$1$$0$$0$$1$$0$$0$$1$$1$$1$$0$$0$$1$$0$$0$$1$$1$$1$$0$$0$$1$$0$$1$$0$$1$
Figure 2: DFA $\mathcal{A}$ constructed for the L-reduction of 2STCON to
2Minimal-DFA. The $j$-transitions exiting states of the form $i_{j}$ are only
indicated.

First, note that the idea of the $p$\- and $q$-states is similar to the known
L-reduction of 2STCON to 3Minimal-DFA. The $p$-states are used to access every
state in $Q$, thus avoiding unreachable states. The $q$-states are used to
allow the return to $0$ from every state.

Second, we cannot use an additional letter to switch from $p_{i}$ to $i$ to
$q_{i}$. Thus, letter $1$ is used to leave the $p$-states and to exit $q_{0}$
to state $0$. Letter $0$ is used to advance to the next layer in both the
$p$\- and $q$-states. To allow switching from the $v$-states to the
$q$-states, we introduce for each $i\in Q^{\prime}$ a component consisting of
$i$ and the two branches $i_{0}^{\prime},i_{0}$ and $i_{1}^{\prime},i_{1}$.
The states $i_{0}^{\prime},i_{1}^{\prime}$ are waiting states used to prove
the non-equivalence of $q$\- and $v$-states. The states $i_{0},i_{1}$
implement on the one hand the original transitions in $\mathcal{A}^{\prime}$,
that is, $\delta(i_{j},j)=\delta^{\prime}(i,j)$, and on the other hand the
transitions into the $q$-states, that is, $\delta(i_{j},1-j)=q_{i}$.

Third, an extra $q$-state $q_{0}^{\prime}$ is introduced, which is only
directly accessible from $q_{0}$. Without $q_{0}^{\prime}$ the situation
$\delta(1_{1},1)=0=\delta(q_{0},1)$ and
$\delta(1_{1},0)=q_{1}=\delta(q_{0},0)$ would be possible, immediately
implying the non-minimality of $\mathcal{A}$. The introduction of
$q_{0}^{\prime}$ solves this problem.

Note that there is a path from $0$ to $n-1$ in $\mathcal{A}$ iff there is such
a path in $G$. Using this it follows that $\mathcal{A}$ is minimal iff there
exists a path from $0$ to $n-1$ in $G$. Since $\mathcal{A}$ can obviously be
constructed in logarithmic space, the given construction is indeed an
L-reduction of 2STCON to 2Minimal-DFA. Consequently, 2Minimal-DFA is NL-hard.

###  6.2 Complexity of S-Prime-DFA

We end our discussion by using the construction presented in Section 6.1 to
establish complexity boundaries for S-Prime-DFA. First, we define the notion
of S-compositionality.

######  Definition 6.2.

A DFA $\mathcal{A}$ is S-composite if there is a $k\in\mathbb{N}_{\geq
1},k<|\mathcal{A}|$ such that $\mathcal{A}$ is $k$-decomposable. Otherwise,
$\mathcal{A}$ is S-prime.

We denote the problem of deciding S-primality for a given DFA with S-Prime-DFA
and the restriction of S-Prime-DFA to DFAs with at most $k\in\mathbb{N}_{\geq
2}$ letters with kS-Prime-DFA.

Note that the proof used in [12] to show that Prime-DFA is in ExpSpace is
applicable for S-Prime-DFA with only slight modifications. Next, note that the
L-reduction of the emptiness problem for DFAs to Prime-DFA used in [12] to
prove the NL-hardness of Prime-DFA relies on the fact that every DFA
recognizing the empty language is prime. Thus, it is not easily adaptable for
S-Prime-DFA. Instead, the NL-hardness of 2S-Prime-DFA is shown by using a
reduction from 2STCON, which adapts the construction outlined in Section 6.1.
We get:

######  Theorem 6.3.

The problems S-Prime-DFA and kS-Prime-DFA for $k\in\mathbb{N}_{\geq 2}$ are in
ExpSpace and they are NL-hard.

Further, we denote with kPrime-DFA the restriction of Prime-DFA to DFAs with
at most $k\in\mathbb{N}_{\geq 2}$ letters and remark that the results
presented in [12] can be expanded to:

######  Theorem 6.4.

The problems Prime-DFA and kPrime-DFA for $k\in\mathbb{N}_{\geq 2}$ are in
ExpSpace and they are NL-hard.

This ends our discussion of the complexity of S-Prime-DFA and its
restrictions, in which we have applied the construction outlined in Section
6.1 to prove NL-hardness.

##  7 Discussion

We studied the intersection compositionality, also denoted with
$\cap$-compositionality, of regular languages. We added to the existing line
of research focusing on fragments of the regular languages by analyzing the
$\cap$-compositionality of ADFAs and thereby of finite languages. This
research was in part motivated by existing results concerning the
concatenation compositionality of finite languages.

We completely characterized the $\cap$-compositionality of ADFAs and thus
finite languages. Using this characterization we proved the NL-completeness of
$\textsc{Prime-DFA}_{\text{fin}}$. Thus, finite languages are significantly
easier to handle under $\cap$-compositionality than under concatenation
compositionality, where the respective primality problem for finite languages
is NP-hard [18].

With notions of compositionality using union and both union and intersection
already suggested in [12], we formally introduced the notions of $\cup$\- and
DNF-compositionality. We characterized the $\cup$\- and DNF-compositionality
of finite languages, which proved to be far simpler than the characterization
of $\cap$-compositionality. These results also imply the characterization of
the $\cap$-, $\cup$\- and DNF-compositionality of co-finite languages.

This suggests that the key feature of finite languages regarding
compositionality is not the finiteness of the languages per se, but rather the
existence of only finitely many meaningfully different runs of the respective
DFAs, a feature finite languages have in common not only with co-finite
languages, but also with languages whose minimal DFAs allow for cycles in both
accepting and rejecting sinks. A logical next step would therefore be the
characterization of the compositionality of these DFAs.

We also note that in our proofs we employed $\cap$-compositionality results
concerning a different language fragment, namely co-safety DFAs, studied in
[12]. This suggests the possibility of employing the results concerning finite
languages in future analyses and stresses the usefulness of working with
language fragments. We provided one application of the results concerning
finite languages by using them to prove the existence of a language that is
DNF-composite but $\cap$\- and $\cup$-prime.

Furthermore, we presented a proof of the NL-hardness and thereby NL-
completeness of the basic problem 2Minimal-DFA. While the NL-hardness of
kMinimal-DFA for $k\in\mathbb{N}_{\geq 3}$ is folklore, this result appears to
be new.

We utilized this result to establish the known complexity boundaries of Prime-
DFA for the here newly introduced problem S-Prime-DFA. We extended these
results to the restrictions kPrime-DFA and kS-Prime-DFA for
$k\in\mathbb{N}_{\geq 2}$.

While it is interesting that a slight variation in the definition of
$\cap$-compositionality, which does not touch the validity of most results,
requires a whole new approach to establish the known lower complexity
boundary, the big task of closing the doubly exponential complexity gap for
Prime-DFA still remains. And now, this gap exists for S-Prime-DFA as well.

Therefore, with the analysis of language fragments, further notions of
compositionality, and the complexity gaps for Prime-DFA and S-Prime-DFA, there
is still need for further research.

## References

  * [1] Christel Baier and Joost-Pieter Katoen.  Principles of model checking.  MIT Press, 2008.  URL: https://mitpress.mit.edu/9780262026499/principles-of-model-checking/.
  * [2] Sang Cho and Dung T. Huynh.  The parallel complexity of finite-state automata problems.  Inf. Comput., 97(1):1–22, 1992.  doi:10.1016/0890-5401(92)90002-W.
  * [3] Willem P. de Roever, Hans Langmaack, and Amir Pnueli, editors.  Compositionality: The Significant Difference, International Symposium, COMPOS’97, Bad Malente, Germany, September 8-12, 1997. Revised Lectures, volume 1536 of Lecture Notes in Computer Science. Springer, 1998\.  doi:10.1007/3-540-49213-5.
  * [4] Henning Fernau and Markus Holzer.  Personal communication.
  * [5] Peter Gazi and Branislav Rovan.  Assisted problem solving and decompositions of finite automata.  In Viliam Geffert, Juhani Karhumäki, Alberto Bertoni, Bart Preneel, Pavol Návrat, and Mária Bieliková, editors, SOFSEM 2008: Theory and Practice of Computer Science, 34th Conference on Current Trends in Theory and Practice of Computer Science, Nový Smokovec, Slovakia, January 19-25, 2008, Proceedings, volume 4910 of Lecture Notes in Computer Science, pages 292–303. Springer, 2008.  doi:10.1007/978-3-540-77566-9\\_25.
  * [6] E. Mark Gold.  Complexity of automaton identification from given data.  Inf. Control., 37(3):302–320, 1978.  doi:10.1016/S0019-9958(78)90562-4.
  * [7] Neil Immerman.  Nondeterministic space is closed under complementation.  SIAM J. Comput., 17(5):935–938, 1988.  doi:10.1137/0217058.
  * [8] Neil Immerman.  Descriptive complexity.  Graduate texts in computer science. Springer, 1999.  doi:10.1007/978-1-4612-0539-5.
  * [9] Ismaël Jecker, Orna Kupferman, and Nicolas Mazzocchi.  Unary prime languages.  In Javier Esparza and Daniel Král’, editors, 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020, August 24-28, 2020, Prague, Czech Republic, volume 170 of LIPIcs, pages 51:1–51:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.  doi:10.4230/LIPIcs.MFCS.2020.51.
  * [10] Ismaël Jecker, Nicolas Mazzocchi, and Petra Wolf.  Decomposing permutation automata.  In Serge Haddad and Daniele Varacca, editors, 32nd International Conference on Concurrency Theory, CONCUR 2021, August 24-27, 2021, Virtual Conference, volume 203 of LIPIcs, pages 18:1–18:19. Schloss Dagstuhl \- Leibniz-Zentrum für Informatik, 2021.  doi:10.4230/LIPIcs.CONCUR.2021.18.
  * [11] Neil D. Jones.  Space-bounded reducibility among combinatorial problems.  J. Comput. Syst. Sci., 11(1):68–85, 1975.  doi:10.1016/S0022-0000(75)80050-X.
  * [12] Orna Kupferman and Jonathan Mosheiff.  Prime languages.  Inf. Comput., 240:90–107, 2015.  doi:10.1016/j.ic.2014.09.010.
  * [13] Niklas Lauffer, Beyazit Yalcinkaya, Marcell Vazquez-Chanlatte, Ameesh Shah, and Sanjit A. Seshia.  Learning deterministic finite automata decompositions from examples and demonstrations.  In Alberto Griggio and Neha Rungta, editors, 22nd Formal Methods in Computer-Aided Design, FMCAD 2022, Trento, Italy, October 17-21, 2022, pages 1–6. IEEE, 2022.  doi:10.34727/2022/isbn.978-3-85448-053-2\\_39.
  * [14] Wim Martens, Matthias Niewerth, and Thomas Schwentick.  Schema design for XML repositories: complexity and tractability.  In Jan Paredaens and Dirk Van Gucht, editors, Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2010, June 6-11, 2010, Indianapolis, Indiana, USA, pages 239–250. ACM, 2010.  doi:10.1145/1807085.1807117.
  * [15] Alexandru Mateescu, Arto Salomaa, and Sheng Yu.  Factorizations of languages and commutativity conditions.  Acta Cybern., 15(3):339–351, 2002.  URL: https://cyber.bibl.u-szeged.hu/index.php/actcybern/article/view/3583.
  * [16] Alon Netser.  Decomposition of safe languages.  Amirim Research Project Report from the Hebrew University, 2018\.
  * [17] Arto Salomaa and Sheng Yu.  On the decomposition of finite languages.  In Grzegorz Rozenberg and Wolfgang Thomas, editors, Developments in Language Theory, Foundations, Applications, and Perspectives, Aachen, Germany, 6-9 July 1999, pages 22–31. World Scientific, 1999.  doi:10.1142/9789812792464\\_0003.
  * [18] Philip Sieder.  A lower bound for primality of finite languages.  CoRR, abs/1902.06253, 2019.  URL: http://arxiv.org/abs/1902.06253, arXiv:1902.06253.
  * [19] Stavros Tripakis.  Compositionality in the science of system design.  Proc. IEEE, 104(5):960–972, 2016.  doi:10.1109/JPROC.2015.2510366.
  * [20] Moshe Y. Vardi and Pierre Wolper.  An automata-theoretic approach to automatic program verification (preliminary report).  In Proceedings of the Symposium on Logic in Computer Science (LICS ’86), Cambridge, Massachusetts, USA, June 16-18, 1986, pages 332–344. IEEE Computer Society, 1986.  URL: https://hdl.handle.net/2268/116609.
  * [21] Wojciech Wieczorek.  An algorithm for the decomposition of finite languages.  Log. J. IGPL, 18(3):355–366, 2010.  doi:10.1093/jigpal/jzp032.

##  Appendix A Proofs for Section 3

In this section we provide detailed proofs for the results presented in
Section 3. To increase readability and avoid overlong proofs, we introduce a
number of additional lemmas.

Our goal is to prove Theorem 3.1, which reads: See 3.1 In order to prove
Theorem 3.1 we will follow the structure outlined in the opening of Section 3.
That is, we prove the following five assertions one after another: See 1 Note
that (1)-(1) cover the entire set of minimal ADFAs recognizing a non-empty
language. Therefore, proving (1)-(1) is sufficient to prove Theorem 3.1.
Further, note that a DFA recognizing the empty language is trivially prime.
Therefore, Theorem 3.1 indeed characterizes the compositionality of ADFAs and
thereby of finite languages.

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

###  A.1 Proofs of 1 (1) and (1)

We begin by presenting the rather simple proofs of 1 (1) and (1).

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

Assume that $\mathcal{A}$ is not linear. As mentioned in Section 2, this
implies $\text{ind}(\mathcal{A})>n+2$.

For a word $w\in\Sigma^{*}$, let $\mathcal{A}_{w}$ be the minimal DFA with
$\mathcal{L}(\mathcal{A}_{w})=\\{w\\}$. For a value $m\in\mathbb{N}$, let
$\mathcal{A}_{\leq m}$ be the minimal DFA with $\mathcal{L}(\mathcal{A}_{\leq
m})=\\{w\in\Sigma^{*}\hskip 5.69054pt|\hskip 5.69054pt|w|\leq m\\}$. The
trivial constructions are pictured in Figure 3. Note that
$|\mathcal{A}_{w}|=|w|+2$ and $|\mathcal{A}_{\leq m}|=m+2$.

$q_{0}$$q_{1}$$q_{2}$$q_{m-1}$$q_{m}$$\sigma_{1}$$\sigma_{2}$$\sigma_{m}$ (a)
$\mathcal{A}_{w}$ with $\mathcal{L}(\mathcal{A}_{w})=\\{w\\}$ for a word
$w=\sigma_{1}\dots\sigma_{m}\in\Sigma^{m}$, where $m\in\mathbb{N}$.

$q_{0}$$q_{1}$$q_{2}$$q_{m-1}$$q_{m}$$\Sigma$$\Sigma$$\Sigma$ (b)
$\mathcal{A}_{\leq m}$ with $\mathcal{L}(\mathcal{A}_{\leq
m})=\\{w\in\Sigma^{*}\hskip 5.69054pt|\hskip 5.69054pt|w|\leq m\\}$, where
$m\in\mathbb{N}$.

Figure 3: DFAs $\mathcal{A}_{w}$ and $\mathcal{A}_{\leq m}$. Omitted
transitions lead to a rejecting sink.

Define $L^{\prime}=\\{w\in\Sigma^{*}\hskip 5.69054pt|\hskip
5.69054ptw\in\overline{\mathcal{L}(\mathcal{A})}\text{ and }|w|\leq n\\}$. We
proof: $\mathcal{L}(\mathcal{A})=\mathcal{L}(\mathcal{A}_{\leq
n})\cap\bigcap_{w\in L^{\prime}}\mathcal{L}(\overline{\mathcal{A}_{w}})$,
where $\overline{\mathcal{A}_{w}}$ is the complement DFA of $\mathcal{A}_{w}$.
Note that this immediately implies the compositionality of $\mathcal{A}$,
since $|\mathcal{A}_{\leq n}|=n+2<\text{ind}(\mathcal{A})$ and
$|\overline{\mathcal{A}_{w}}|=|w|+2\leq n+2<\text{ind}(\mathcal{A})$ for each
$w\in L^{\prime}$.

We begin by proving
$\mathcal{L}(\mathcal{A})\subseteq\mathcal{L}(\mathcal{A}_{\leq
n})\cap\bigcap_{w\in L^{\prime}}\mathcal{L}(\overline{\mathcal{A}_{w}})$. Let
$w\in\mathcal{L}(\mathcal{A})$. Then $|w|\leq n$ holds and therefore we have
$w\in\mathcal{L}(\mathcal{A}_{\leq n})$. Let $w^{\prime}\in L^{\prime}$. In
particular, this implies $w^{\prime}\notin\mathcal{L}(\mathcal{A})$ and thus
$w^{\prime}\neq w$. Therefore,
$w\in\mathcal{L}(\overline{\mathcal{A}_{w^{\prime}}})$. Taken together we get
$w\in\mathcal{L}(\mathcal{A}_{\leq n})\cap\bigcap_{w\in
L^{\prime}}\mathcal{L}(\overline{\mathcal{A}_{w}})$. The first containment is
shown.

Next, we prove $\mathcal{L}(\mathcal{A}_{\leq n})\cap\bigcap_{w\in
L^{\prime}}\mathcal{L}(\overline{\mathcal{A}_{w}})\subseteq\mathcal{L}(\mathcal{A})$.
Let $w\notin\mathcal{L}(\mathcal{A})$. If $|w|>n$ then
$w\notin\mathcal{L}(\mathcal{A}_{\leq n})$. On the other hand, if $|w|\leq n$
we have $w\in L^{\prime}$ and therefore $w\notin\bigcap_{w\in
L^{\prime}}\mathcal{L}(\overline{\mathcal{A}_{w}})$. Taken together we get
$w\notin\mathcal{L}(\mathcal{A}_{\leq n})\cap\bigcap_{w\in
L^{\prime}}\mathcal{L}(\overline{\mathcal{A}_{w}})$. The second containment is
shown and we are done.

For the proof of 1 (1) we introduce an additional lemma, which we will reuse
when proving Theorem 5.2 (5.2).

######  Lemma A.2.

Let $\mathcal{B}=(S,\Sigma,s_{I},\eta,G)$ be a minimal DFA such that there
exists an $m\in\mathbb{N}$ with $\text{ind}(\mathcal{B})<m+2$ and
$\sigma^{m}\in\mathcal{L}(\mathcal{B})$ for a letter $\sigma\in\Sigma$. Then
there exists an $l\in\\{1,\dots,m+1\\}$ such that
$\eta(s_{I},\sigma^{m+il})=\eta(s_{I},\sigma^{m})$ for every $i\in\mathbb{N}$.

######  Proof A.3.

Let $\mathcal{B}$ and $m$ be as required. Let $s=\eta(s_{I},\sigma^{m})$.

Case 1: In the initial run of $\mathcal{B}$ on $\sigma^{m}$ no state is
visited more than once.

Since $\text{ind}(\mathcal{B})<m+2$, we have $\text{ind}(\mathcal{B})=m+1$ and
in the initial run of $\mathcal{B}$ on $\sigma^{m}$ every state of
$\mathcal{B}$ is visited exactly once. Then there exists a
$j\in\\{0,\dots,m\\}$ such that
$\eta(s_{I},\sigma^{m}\sigma)=\eta(s_{I},\sigma^{j})$. Select $l=m+1-j$.
Clearly, $1\leq l\leq m+1$ holds. Additionally, we have
$\eta(s,\sigma^{l})=\eta(s,\sigma^{m+1-j})=\eta(s,\sigma\sigma^{m-j})=\eta(\eta(s_{I},\sigma^{m}),\sigma\sigma^{m-j})=\eta(\eta(s_{I},\sigma^{m}\sigma),\sigma^{m-j})=\eta(\eta(s_{I},\sigma^{j}),\sigma^{m-j})=\eta(s_{I},\sigma^{j}\sigma^{m-j})=\eta(s_{I},\sigma^{m})=s$.

We now argue that the selected $l$ satisfies the requirement using induction.
For $i=0$, we have $\eta(s_{I},\sigma^{m+il})=\eta(s_{I},\sigma^{m})=s$. Now
assume that $\eta(s_{I},\sigma^{m+il})=s$ holds for a particular
$i\in\mathbb{N}$. Then we have
$\eta(s_{I},\sigma^{m+(i+1)l})=\eta(s_{I},\sigma^{m+il}\sigma^{l})=\eta(\eta(s_{I},\sigma^{m+il}),\sigma^{l})=\eta(s,\sigma^{l})=s$.
We are done with Case 1.

Case 2: Else.

Then there exist $s,t\in\\{0,\dots,m\\}$ with $s<t$ such that
$\eta(s_{I},\sigma^{s})=\eta(s_{I},\sigma^{t})$. Then
$\eta(s_{I},\sigma^{s+(m-t)+1})=\eta(s_{I},\sigma^{t+(m-t)+1})=\eta(s_{I},\sigma^{m}\sigma)$
holds. Select $j=s+(m-t)+1$. Note that $1\leq j\leq m$.

Thus, we have a $j\in\\{1,\dots,m\\}\subseteq\\{0,\dots,m\\}$ such that
$\eta(s_{I},\sigma^{m}\sigma)=\eta(s_{I},\sigma^{j})$. We can select $l=m+1-j$
and trace back Case 2 to Case 1. Therefore, we are done with Case 2.

With Cases 1 and 2 the proof is complete.

With Lemma A.2 in hand, we can now turn to 1 (1).

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

Assume that $\mathcal{A}$ is linear and that there exists a letter
$\sigma\in\Sigma$ with $\sigma^{n}\in L$. We show that $\sigma^{n+(n+1)!}$ is
a primality witness of $\mathcal{A}$. Note that the linearity of $\mathcal{A}$
implies $\text{ind}(\mathcal{A})=n+2$.

Let $\mathcal{B}=(S,\Sigma,s_{I},\eta,G)\in\alpha(\mathcal{A})$. By
definition, $\mathcal{B}$ is a minimal DFA with
$\text{ind}(\mathcal{B})<\text{ind}(\mathcal{A})=n+2$ and
$\mathcal{L}(\mathcal{A})\subseteq\mathcal{L}(\mathcal{B})$. In particular, we
have $\sigma^{n}\in\mathcal{L}(\mathcal{B})$.

With Lemma A.2 this implies the existence of an $l\in\\{1,\dots,n+1\\}$ such
that $\eta(s_{I},\sigma^{n+il})=\eta(s_{I},\sigma^{n})$ for every
$i\in\mathbb{N}$. In particular, this implies
$\sigma^{n+(n+1)!}\in\mathcal{L}(\mathcal{B})$.

Thus, the word $\sigma^{n+(n+1)!}$ is accepted by every DFA in
$\alpha(\mathcal{A})$. With $\sigma^{n+(n+1)!}\notin\mathcal{L}(\mathcal{A})$
the word $\sigma^{n+(n+1)!}$ is a primality witness of $\mathcal{A}$. We are
done.

To summarize, we have proven 1 (1) and (1). Additionally, with Lemma A.2 we
have established a result that we can reuse in the proof of Theorem 5.2 (5.2).

For now, we have to prove the remaining 1 (1)-(1). From here on, we assume
that $\mathcal{A}$ is linear and that
$\sigma^{n}\notin\mathcal{L}(\mathcal{A})$ holds for every $\sigma\in\Sigma$,
as otherwise we have already covered the compositionality of $\mathcal{A}$
with 1 (1) and (1).

As in Section 3, we assume w.l.o.g. $Q=\\{q_{0},\dots,q_{n+1}\\}$ with $q_{j}$
being reachable from $q_{i}$ for all $i<j$, which implies $q_{I}=q_{0}$ and
$q_{n}\in F$ with $q_{n+1}$ being the rejecting sink. Furthermore, we define
$\Sigma_{i,j}=\\{\sigma\in\Sigma\hskip 5.69054pt|\hskip
5.69054pt\delta(q_{i},\sigma)=q_{j}\\}$. Note that for every $\sigma\in\Sigma$
there exists an $i\in\\{1,\dots,n\\}$ with $\sigma\notin\Sigma_{i-1,i}$. The
form of $\mathcal{A}$ is pictured in Figure 4.

$q_{0}$$q_{1}$$q_{2}$$q_{n-1}$$q_{n}$$q_{n+1}$$\Sigma_{0,1}$$\Sigma_{0,2}$$\Sigma_{0,n-1}$$\Sigma_{0,n}$$\Sigma_{0,n+1}$$\Sigma_{1,2}$$\Sigma_{1,n-1}$$\Sigma_{1,n}$$\Sigma_{1,n+1}$$\Sigma_{2,n-1}$$\Sigma_{2,n}$$\Sigma_{2,n+1}$$\Sigma_{n-1,n}$$\Sigma_{n-1,n+1}$$\Sigma_{n,n+1}$$\Sigma$
Figure 4: Minimal linear ADFA recognizing a non-empty language, with $n$ being
the length of the longest accepted word.

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

We turn to the proof of 1 (1). We assume that $\mathcal{A}$ is not a safety
DFA, which implies $\\{q_{n}\\}\subseteq F\subset Q\setminus\\{q_{n+1}\\}$.
Let $d\in\\{0,\dots,n-1\\}$ with $q_{d}\notin F$. We provide more details on
the DFAs outlined in Section 3.1, which taken together witness the
compositionality of $\mathcal{A}$.

We begin by proving Lemmas 3.2, 3.3 and 3.4. Afterwards, we will prove Lemma
3.5 by providing four additional lemmas for the four cases mentioned in
Section 3.1.

Note Figure 5, which is partly a repetition of Figure 1 and which outlines the
DFA constructions. Additionally, we now provide formal definitions for these
DFAs.

Definition of $\mathcal{A}_{0}$, outlined in Figure 5(a).

We define $\mathcal{A}_{0}=(Q_{0},\Sigma,q_{0},\delta_{0},F_{0})$ where:

$\displaystyle Q_{0}$ $\displaystyle=Q\setminus\\{q_{n}\\}$ $\displaystyle
F_{0}$ $\displaystyle=(F\cup\\{q_{0}\\})\setminus\\{q_{n}\\}$
$\displaystyle\delta_{0}(q,\sigma)$ $\displaystyle=\begin{cases}q_{0}&\text{
if $\delta(q,\sigma)=q_{n}$}\\\ \delta(q,\sigma)&\text{ else, thus if
$\delta(q,\sigma)\neq q_{n}$}\end{cases}.$

Definition of $\hat{\mathcal{A}}_{d}$, outlined in Figure 5(b).

We define
$\hat{\mathcal{A}}=(\hat{Q}_{d},\Sigma,q_{0},\hat{\delta}_{d},\hat{F}_{d})$
where:

$\displaystyle\hat{Q}_{d}$ $\displaystyle=Q\setminus\\{q_{n+1}\\}$
$\displaystyle\hat{F}_{d}$ $\displaystyle=F$
$\displaystyle\hat{\delta}_{d}(q_{i},\sigma)$
$\displaystyle=\begin{cases}q_{d}&\text{ if $i=n$}\\\ q_{n}&\text{ if $i<n$
and $\delta(q_{i},\sigma)=q_{n+1}$}\\\ &\text{ (arbitrary definition
possible)}\\\ \delta(q_{i},\sigma)&\text{ else, thus if $i<n$ and
$\delta(q_{i},\sigma)\neq q_{n+1}$}\end{cases}.$

Definition of $\mathcal{A}_{\underline{i}}$ for $m<n-1$, outlined in Figure
5(c).

Let $m<n-1$ and $\underline{i}=(i_{0},\dots,i_{m})\in I_{m}$. We define
$\mathcal{A}_{\underline{i}}=(Q_{\underline{i}},\Sigma,q_{0},\delta_{\underline{i}},F_{\underline{i}})$
where:

$\displaystyle Q_{\underline{i}}$
$\displaystyle=\\{q_{i_{0}},\dots,q_{i_{m}}\\}\cup\\{q_{n+1},q_{+}\\}$
$\displaystyle F_{\underline{i}}$
$\displaystyle=Q_{\underline{i}}\setminus\\{q_{n+1}\\}$
$\displaystyle\delta_{\underline{i}}(q,\sigma)$
$\displaystyle=\begin{cases}q_{i_{j+1}}&\text{ if $q=q_{i_{j}}$ for $j<m$ and
$\sigma\in\Sigma_{i_{j},i_{j+1}}$}\\\ q_{+}&\text{ if $q=q_{i_{j}}$ for $j<m$
and $\sigma\notin\Sigma_{i_{j},i_{j+1}}$}\\\ q_{n+1}&\text{ if
$q=q_{i_{m}}$}\\\ q&\text{ else, thus if
$q\in\\{q_{n+1},q_{+}\\}$}\end{cases}.$

Definition of $\hat{\mathcal{A}}_{d}$ for $m=n-1$, outlined in Figure 5(d).

Let $m=n-1$ and $\underline{i}=(0,\dots,j-1,j+1,\dots,n)\in I_{m}$. We define
$\mathcal{A}_{\underline{i}}=(Q_{\underline{i}},\Sigma,q_{0},\delta_{\underline{i}},F_{\underline{i}})$
where:

$\displaystyle Q_{\underline{i}}$
$\displaystyle=\\{q_{0},\dots,q_{j-1},q_{j+1},\dots,q_{n+1}\\}$ $\displaystyle
F_{\underline{i}}$ $\displaystyle=Q_{\underline{i}}\setminus\\{q_{n+1}\\}$
$\displaystyle\delta_{\underline{i}}(q_{k},\sigma)=$
$\displaystyle\begin{cases}q_{k+1}&\text{ if $k<n+1$ and $k\neq j-1$ and
$\sigma\in\Sigma_{k,k+1}$}\\\ q_{k}&\text{ if $k<n+1$ and $k\neq j-1$ and
$\sigma\notin\Sigma_{k,k+1}$}\\\ q_{j+1}&\text{ if $k=j-1$ and
$\sigma\in\Sigma_{j-1,j+1}$}\\\ q_{j-1}&\text{ if $k=j-1$ and
$\sigma\notin\Sigma_{j-1,j+1}$}\\\ q_{n+1}&\text{ else, thus if
$k=n+1$}\end{cases}.$

Definition of $\mathcal{A}_{\sigma,i}$, outlined in Figure 5(e).

Let $\sigma\in\Sigma$ and $i\in\\{1,\dots,n\\}$. We define
$\mathcal{A}_{\sigma,i}=(Q_{\sigma,i},\Sigma,q_{0},\delta_{\sigma,i},F_{\sigma,i})$
where:

$\displaystyle Q_{\sigma,i}$ $\displaystyle=\\{q_{0},\dots,q_{n}\\}$
$\displaystyle F_{\sigma,i}$ $\displaystyle=Q_{\sigma,i}\setminus\\{q_{n}\\}$
$\displaystyle\delta(q_{j},\sigma^{\prime})$
$\displaystyle=\begin{cases}q_{i}&\text{ if $j=i-1$ and
$\sigma^{\prime}=\sigma$}\\\ q_{i-1}&\text{ if $j=i-1$ and
$\sigma^{\prime}\neq\sigma$}\\\ q_{j+1}&\text{ if $j\neq i-1$ and $j<n$}\\\
q_{n}&\text{ else, thus if $j=n$}\end{cases}.$

Definition of $\mathcal{A}_{w}^{!}$, outlined in Figure 5(f).

Let $w=\sigma_{1}\dots\sigma_{m}\in\Sigma^{m}$. We define
$\mathcal{A}_{w}^{!}=(Q_{w}^{!},\Sigma,q_{0},\delta_{w}^{!},F_{w}^{!})$ where:

$\displaystyle Q_{w}^{!}$ $\displaystyle=\\{q_{0},\dots,q_{m}\\}$
$\displaystyle F_{w}^{!}$ $\displaystyle=Q_{w}^{!}\setminus\\{q_{m}\\}$
$\displaystyle\delta_{w}^{!}(q_{i},\sigma)$
$\displaystyle=\begin{cases}q_{i+1}&\text{if $i<m$ and
$\sigma=\sigma_{i+1}$}\\\ q_{i}&\text{if $i<m$ and
$\sigma\neq\sigma_{i+1}$}\\\ q_{m}&\text{else, thus if $i=m$}\end{cases}.$

$q_{0}$$q_{1}$$q_{n-1}$$q_{n+1}$$\Sigma_{0,1}$$\Sigma_{0,n-1}$$\Sigma_{0,n+1}$$\Sigma_{0,n}$$\Sigma_{1,n-1}$$\Sigma_{1,n+1}$$\Sigma_{1,n}$$\Sigma_{n-1,n+1}$$\Sigma_{n-1,n}$$\Sigma$
(a) $\mathcal{A}_{0}$.

$q_{0}$$q_{d}$$q_{n-1}$$q_{n}$$\Sigma_{0,n},\Sigma_{0,n+1}$$\Sigma_{d,n},\Sigma_{d,n+1}$$\Sigma_{n-1,n},\Sigma_{n-1,n+1}$$\Sigma$
(b) $\hat{\mathcal{A}}_{d}$. Unaltered transitions are omitted.

$q_{0}$$q_{i_{1}}$$q_{i_{m-1}}$$q_{n}$$q_{n+1}$$q_{+}$$\Sigma_{0,i_{1}}$$\overline{\Sigma_{0,i_{1}}}$$\overline{\Sigma_{i_{1},i_{2}}}$$\Sigma_{i_{m-1},n}$$\overline{\Sigma_{i_{m-1},n}}$$\Sigma$$\Sigma$$\Sigma$
(c) $\mathcal{A}_{\underline{i}}$ if $m<n-1$.

$q_{0}$$q_{j-1}$$q_{j+1}$$q_{n}$$q_{n+1}$$\overline{\Sigma_{0,1}}$$\Sigma_{j-1,j+1}$$\overline{\Sigma_{j-1,j+1}}$$\overline{\Sigma_{j+1,j+2}}$$\Sigma$$\Sigma$
(d) $\mathcal{A}_{\underline{i}}$ if $m=n-1$, where
$\underline{i}=(0,\dots,j-1,j+1,\dots,n)$.

$q_{0}$$q_{1}$$q_{i-1}$$q_{i}$$q_{n-1}$$q_{n}$$\Sigma$$\Sigma$$\Sigma\setminus\\{\sigma\\}$$\sigma$$\Sigma$$\Sigma$$\Sigma$
(e) $\mathcal{A}_{\sigma,i}$.

$q_{0}$$q_{1}$$q_{m-2}$$q_{m-1}$$q_{m}$$\sigma_{1}$$\Sigma\setminus\\{\sigma_{1}\\}$$\Sigma\setminus\\{\sigma_{2}\\}$$\sigma_{m-1}$$\Sigma\setminus\\{\sigma_{m-1}\\}$$\sigma_{m}$$\Sigma\setminus\\{\sigma_{m}\\}$$\Sigma$
(f) $\mathcal{A}_{w}^{!}$.

Figure 5: DFAs $\mathcal{A}_{0}$ and $\hat{\mathcal{A}}_{d}$. DFA
$\mathcal{A}_{\underline{i}}$ for $\underline{i}\in I_{m}$ with
$m\in\\{1,\dots,n-1\\}$. DFA $\mathcal{A}_{\sigma,i}$ for
$\sigma\in\Sigma,i\in\\{1,\dots,n\\}$. DFA $\mathcal{A}_{w}^{!}$ for
$w=\sigma_{1}\dots\sigma_{m}\in\Sigma^{m}$.

First, we consider Lemma 3.2, which reads: See 3.2

######  Proof A.5 (Proof of Lemma 3.2).

We begin by looking at (i).

First, consider $\mathcal{A}_{0}=(Q_{0},\Sigma,q_{0},\delta_{0},F_{0})$. As
seen in Figure 5(a), we have
$|\mathcal{A}_{0}|=n+1<n+2=\text{ind}(\mathcal{A})$. It remains to show that
$\mathcal{L}(\mathcal{A})\subseteq\mathcal{L}(\mathcal{A}_{0})$. Let
$w\in\mathcal{L}(\mathcal{A})$. Then there exists an $i\in\\{0,\dots,n\\}$
with $\delta(q_{0},w)=q_{i}$ and $q_{i}\in F$. If $i<n$ we obviously have
$\delta_{0}(q_{0},w)=q_{i}$ and $q_{i}\in F_{0}$ as well. If $i=n$ then
$\delta_{0}(q_{0},w)=q_{0}\in F_{0}$ holds. Therefore, we have
$w\in\mathcal{L}(\mathcal{A}_{0})$. We have shown
$\mathcal{A}_{0}\in\alpha(\mathcal{A}_{0})$.

Second, consider
$\hat{\mathcal{A}}_{d}=(\hat{Q}_{d},\Sigma,q_{0},\hat{\delta}_{d},\hat{F}_{d})$.
As seen in Figure 5(b), we again have
$|\hat{\mathcal{A}}_{d}|=n+1<n+2=\text{ind}(\mathcal{A})$. We need to show
that $\mathcal{L}(\mathcal{A})\subseteq\mathcal{L}(\hat{\mathcal{A}}_{d})$.
Let $w\in\mathcal{L}(\mathcal{A})$. Then there exists an $i\in\\{0,\dots,n\\}$
with $\delta(q_{0},w)=q_{i}$ and $q_{i}\in F$. Obviously, we have
$\hat{\delta}_{d}(q_{0},w)=q_{i}\in\hat{F}_{d}$ and thus
$w\in\mathcal{L}(\hat{\mathcal{A}}_{d})$. We have shown
$\hat{\mathcal{A}}_{d}\in\alpha(\mathcal{A})$.

Third, consider
$\mathcal{A}_{\underline{i}}=(Q_{\underline{i}},\Sigma,q_{0},\delta_{\underline{i}},F_{\underline{i}})$
for an $\underline{i}=(i_{0},\dots,i_{m})\in I_{m}$ where
$m\in\\{1,\dots,n-1\\}$.

We begin by assuming $m<n-1$. As seen in Figure 5(c), we have
$|\mathcal{A}_{\underline{i}}|=m+3<(n-1)+3=n+2=\text{ind}(\mathcal{A})$. We
need to show that
$\mathcal{L}(\mathcal{A})\subseteq\mathcal{L}(\mathcal{A}_{\underline{i}})$.
Let $w=\sigma_{1}\dots\sigma_{l}\in\Sigma^{l}$ with
$w\notin\mathcal{L}(\mathcal{A}_{\underline{i}})$. Clearly, this implies $l>m$
with
$\sigma_{1}\in\Sigma_{i_{0},i_{1}},\dots,\sigma_{m}\in\Sigma_{i_{m-1},i_{m}}$.
Therefore, we have $\delta(q_{0},\sigma_{1}\dots\sigma_{m})=q_{n}$ and thus
$\delta(q_{0},w)=q_{n+1}$. Thus, we have $w\notin\mathcal{L}(\mathcal{A})$. We
have shown $\mathcal{A}_{\underline{i}}\in\alpha(\mathcal{A})$ if $m<n-1$.

Next, we assume $m=n-1$. As seen in Figure 5(d), we have
$|\mathcal{A}_{\underline{i}}|=m+2=(n-1)+2=n+1<n+2=\text{ind}(\mathcal{A})$.
Again, it remains to show that
$\mathcal{L}(\mathcal{A})\subseteq\mathcal{L}(\mathcal{A}_{\underline{i}})$.
Let $w=\sigma_{1}\dots\sigma_{l}\in\Sigma^{l}$ with
$w\notin\mathcal{L}(\mathcal{A}_{\underline{i}})$. Clearly, this implies
$l\geq n$. If $l>n$ it trivially follows that
$w\notin\mathcal{L}(\mathcal{A})$. If $l=n$ we have
$\sigma_{1}\in\Sigma_{0,1},\dots,\sigma_{j-1}\in\Sigma_{j-2,j-1}$ and
$\sigma_{j}\in\Sigma_{j-1,j+1}$ and
$\sigma_{j+1}\in\Sigma_{j+1,j+2},\dots,\sigma_{n}\in\Sigma_{n,n+1}$, where $j$
is the one value in $\\{0,\dots,n\\}\setminus\\{i_{0},\dots,i_{n-1}\\}$.
Therefore, we have $\delta(q_{0},w)=q_{n+1}$ and thus
$w\notin\mathcal{L}(\mathcal{A})$. We have shown
$\mathcal{A}_{\underline{i}}\in\alpha(\mathcal{A})$ if $m=n-1$.

Together we have shown $\mathcal{A}_{\underline{i}}\in\alpha(\mathcal{A})$.
This completes the proof of (i).

We now turn to (ii). Consider a word
$w=\sigma_{1}\dots\sigma_{l}\in\Sigma^{l}$ with $w\notin L$ that is not an
extension of a word $u\in L,|u|=n$. That is, we do not have $l>n$ with
$\delta(q_{0},\sigma_{1}\dots\sigma_{n})=q_{n}$. We need to prove that
$w\notin\mathcal{L}(\mathcal{A}_{0})\cap\mathcal{L}(\hat{\mathcal{A}}_{d})\cap\bigcap_{m=1}^{n-1}\bigcap_{\underline{i}\in
I_{m}}\mathcal{L}(\mathcal{A}_{\underline{i}})$.

If $w\notin\mathcal{L}(\mathcal{A}_{0})\cap\mathcal{L}(\hat{\mathcal{A}}_{d})$
we are done. Therefore, we assume
$w\in\mathcal{L}(\mathcal{A}_{0})\cap\mathcal{L}(\hat{\mathcal{A}}_{d})$. Note
that $w\in\mathcal{L}(\hat{\mathcal{A}}_{d})$ implies
$\delta(q_{0},w)=q_{n+1}$. Further, note that
$w\in\mathcal{L}(\mathcal{A}_{0})$ implies that in the run of $\mathcal{A}$ on
$w$ the sink $q_{n+1}$ is entered from $q_{n}$. That is, there exists an
$m\in\mathbb{N},m<l$ such that
$\delta(q_{0},\sigma_{1}\dots\sigma_{m})=q_{n}$. Since by definition
$\delta(q_{0},\sigma_{1}\dots\sigma_{n})\neq q_{n}$ holds, this implies $m<n$.
This immediately implies the existence of an
$\underline{i}=\\{i_{0},\dots,i_{m}\\}\in I_{m}$ with
$\sigma_{1}\in\Sigma_{i_{0},i_{1}},\dots,\sigma_{m}\in\Sigma_{i_{m-1},i_{m}}$.
Thus, we have $\delta_{\underline{i}}(q_{0},\sigma_{1}\dots\sigma_{m})=q_{n}$
and $\delta_{\underline{i}}(q_{0},w)=q_{n+1}\notin F_{\underline{i}}$ and
therefore $w\notin\mathcal{L}(\mathcal{A}_{\underline{i}})$.

We have shown
$w\notin\mathcal{L}(\mathcal{A}_{0})\cap\mathcal{L}(\hat{\mathcal{A}}_{d})\cap\bigcap_{m=1}^{n-1}\bigcap_{\underline{i}\in
I_{m}}\mathcal{L}(\mathcal{A}_{\underline{i}})$, which completes the proof of
(ii). We are done with the proof of Lemma 3.2.

Next, we consider Lemma 3.3, which reads: See 3.3

######  Proof A.6 (Proof of Lemma 3.3).

Let $\sigma\in\Sigma$ and $i\in\\{1,\dots,n\\}$ with
$\sigma\notin\Sigma_{i-1,i}$. We consider the DFA
$\mathcal{A}_{\sigma,i}=(Q_{\sigma,i},\Sigma,q_{0},\delta_{\sigma,i},F_{\sigma,i})$.

First, we consider (i) and prove
$\mathcal{A}_{\sigma,i}\in\alpha(\mathcal{A})$. As seen in Figure 5(e), we
have $|\mathcal{A}_{\sigma,i}|=n+1<n+2=\text{ind}(\mathcal{A})$. It remains to
show that
$\mathcal{L}(\mathcal{A})\subseteq\mathcal{L}(\mathcal{A}_{\sigma,i})$. Let
$w=\sigma_{1}\dots\sigma_{m}\in\Sigma^{m}$ with
$w\notin\mathcal{L}(\mathcal{A}_{\sigma,i})$. Note that this implies $|w|\geq
n$. If $|w|>n$ then $w\notin\mathcal{L}(\mathcal{A})$ holds trivially. If
$|w|=n$ then for every $j\in\\{0,\dots,n\\}$ we have
$\delta_{\sigma,i}(q_{0},\sigma_{1}\dots\sigma_{j})=q_{j}$. In particular,
this implies $\sigma_{i}=\sigma$. Therefore, we have a word
$w=\sigma_{1}\dots\sigma_{n}$ with $\sigma_{i}\notin\Sigma_{i-1,i}$, which
implies $w\notin\mathcal{L}(\mathcal{A})$. We have shown
$\mathcal{A}_{\sigma,i}\in\alpha(\mathcal{A})$.

Second, we consider (ii). Let $m\in\mathbb{N}$ and let
$w=\sigma_{1}\dots\sigma_{m}\in\Sigma^{m}$ such that there exists a
$j\in\\{1,\dots,m\\}$ with $j\geq i$, $\sigma_{j}=\sigma$ and $m\geq j+(n-i)$.
We need to show $w\notin\mathcal{L}(\mathcal{A}_{\sigma,i})$.

Note that $\delta_{\sigma,i}(q_{0},\sigma_{1}\dots\sigma_{i-1})=q_{i-1}$.
Clearly, this implies
$\delta_{\sigma,i}(q_{0},\sigma_{1}\dots\sigma_{j})=q_{k}$ for a
$k\in\\{0,\dots,n\\},k\geq i$. Thus, the DFA $\mathcal{A}_{\sigma,i}$ will
enter the rejecting sink $q_{n}$ after reading $n-k$ additional letters. Note
that with $m\geq j+(n-i)$ and $k\geq i$ we have
$|\sigma_{j+1}\dots\sigma_{m}|=m-j\geq n-i\geq n-k$. Thus, we have
$w\notin\mathcal{L}(\mathcal{A}_{\sigma,i})$. We are done with (ii), which
completes the proof of Lemma 3.3.

Finally, we complete our first step of the proof of 1 (1) by proving Lemma
3.4, which reads: See 3.4

######  Proof A.7 (Proof of Lemma 3.4).

Let $w=\sigma_{1}\dots\sigma_{n}\in\Sigma^{n}$ with $w\notin L$. We consider
the DFA
$\mathcal{A}_{w}^{!}=(Q_{w}^{!},\Sigma,q_{0},\delta_{w}^{!},F_{w}^{!})$.

As seen in Figure 5(f), we have
$|\mathcal{A}_{w}^{!}|=|w|+1=n+1<n+2=\text{ind}(\mathcal{A})$. It remains to
show that $\mathcal{L}(\mathcal{A})\subseteq\mathcal{L}(\mathcal{A}_{w}^{!})$.
Let $w^{\prime}=\sigma_{1}^{\prime}\dots\sigma_{m}^{\prime}\in\Sigma^{m}$ with
$w^{\prime}\notin\mathcal{L}(\mathcal{A}_{w}^{!})$. Obviously, this implies
$|w^{\prime}|\geq n$. If $|w^{\prime}|>n$ then
$w^{\prime}\notin\mathcal{L}(\mathcal{A})$ holds trivially. If
$|w^{\prime}|=n$ we have
$\delta_{w}^{!}(q_{0},\sigma_{1}^{\prime}\dots\sigma_{i}^{\prime})=q_{i}$ for
every $i\in\\{0,\dots,n\\}$, which implies $w^{\prime}=w$. Since
$w\notin\mathcal{L}(\mathcal{A})$ holds by definition, we have
$w^{\prime}\notin\mathcal{L}(\mathcal{A})$. We are done.

So far, we have proven Lemmas 3.2, 3.3 and 3.4. Next, we turn to Lemma 3.5,
which reads: See 3.5 We will provide four additional lemmas implementing the
four cases mentioned in Section 3.1. The lemmas get increasingly technical,
but the main idea in all of them is to design for a given word $w$ with
$n<|w|\leq n+(n-2)$, which is an extension of a word $u\in L,|u|=n$, a DFA
$\tilde{\mathcal{A}}_{w}\in\alpha(\mathcal{A})$ rejecting $w$. The DFA
$\tilde{\mathcal{A}}_{w}$ simulates the behavior of $\mathcal{A}$ for states
$q_{0},\dots,q_{d-1}$ and the initial run of $\tilde{\mathcal{A}}_{w}$ on $w$
ends in $q_{d}$, which is the only rejecting state of
$\tilde{\mathcal{A}}_{w}$.

We begin with:

######  Lemma A.8.

Let $m\in\mathbb{N}$ with $n<m\leq n+(n-2)$. Let
$w=\sigma_{1}\dots\sigma_{m}\in\Sigma^{m}$ with $\sigma_{1}\dots\sigma_{n}\in
L$ and $|\sigma_{d+1}\dots\sigma_{m}|_{\sigma_{m}}\leq n-d$.

Let $l=|\sigma_{d+1}\dots\sigma_{m-1}|_{\sigma_{m}}$. Note that
$l=|\sigma_{d+1}\dots\sigma_{m-1}|_{\sigma_{m}}<|\sigma_{d+1}\dots\sigma_{m}|_{\sigma_{m}}\leq
n-d$.

Let $S$ be the set of values $i\in\\{d+1,\dots,m-1\\}$ with
$\sigma_{i}=\sigma_{m}$, that is $S=\\{i\in\\{d+1,\dots,m-1\\}\hskip
5.69054pt|\hskip 5.69054pt\sigma_{i}=\sigma_{m}\\}$. Let $T$ be the set of the
$n-d-l$ smallest values $i\in\\{d+1,\dots,m-1\\}$ with
$\sigma_{i}\neq\sigma_{m}$, that is $T=\\{i\in\\{d+1,\dots,m-1\\}\hskip
5.69054pt|\hskip 5.69054pt|\\{j\in\\{d+1,\dots,m-1\\}\hskip 5.69054pt|\hskip
5.69054pt\sigma_{j}\neq\sigma_{m}\wedge j\leq i\\}|\leq n-d-l\\}$. Note that
$|S|=l<n-d$ and $|T|=n-d-l>0$ and $S\cap T=\emptyset$.

Let $I=\\{i_{1},\dots,i_{n-d}\\}=S\cup T$ with $d+1\leq
i_{1}<\dots<i_{n-d}\leq m-1$. Note that $i_{1}=d+1$ and
$|\sigma_{d+1}\dots\sigma_{i_{n-d}}|_{\sigma_{m}}=l=|\sigma_{d+1}\dots\sigma_{m-1}|_{\sigma_{m}}$
and
$|\sigma_{i_{n-d}+1}\dots\sigma_{m}|_{\sigma_{m}}=1=|\sigma_{m}|_{\sigma_{m}}$.

We define
$\mathcal{A}_{w}^{\prime}=(Q_{w}^{\prime},\Sigma,q_{0},\delta_{w}^{\prime},F_{w}^{\prime})$
as follows:

$\displaystyle Q_{w}^{\prime}$ $\displaystyle=\\{q_{0},\dots,q_{n}\\}$
$\displaystyle F_{w}^{\prime}$
$\displaystyle=Q_{w}^{\prime}\setminus\\{q_{d}\\}$
$\displaystyle\delta_{w}^{\prime}(q_{j},\sigma)$
$\displaystyle=\begin{cases}\delta(q_{j},\sigma)&\text{ if $j<d$ and
$\delta(q_{j},\sigma)\neq q_{n+1}$}\\\ q_{j}&\text{ if $j<d$ and
$\delta(q_{j},\sigma)=q_{n+1}$}\\\ &\text{ (arbitrary definition possible)}\\\
q_{d+1}&\text{ if $j=d$}\\\ q_{j+1}&\text{ if $d<j\leq n-1$ and
$\sigma=\sigma_{i_{j+1-d}}$}\\\ q_{j}&\text{ if $d<j\leq n-1$ and
$\sigma\neq\sigma_{i_{j+1-d}}$}\\\ q_{d}&\text{ if $j=n$ and
$\sigma=\sigma_{m}$}\\\ q_{n}&\text{ else, thus if $j=n$ and
$\sigma\neq\sigma_{m}$}\end{cases}.$

Then the following assertions hold:

$\mathcal{A}_{w}^{\prime}\in\alpha(\mathcal{A})$.

$w\notin\mathcal{L}(\mathcal{A}_{w}^{\prime})$. Making (ii) more specific, the
following holds:

$\displaystyle\delta_{w}^{\prime}(q_{0},\sigma_{1}\dots\sigma_{d})$
$\displaystyle=q_{d}$
$\displaystyle\delta_{w}^{\prime}(q_{0},\sigma_{1}\dots\sigma_{d+1})$
$\displaystyle=q_{d+1}$
$\displaystyle\delta_{w}^{\prime}(q_{0},\sigma_{1}\dots\sigma_{i_{n-d}})$
$\displaystyle=q_{n}$
$\displaystyle\delta_{w}^{\prime}(q_{0},\sigma_{1}\dots\sigma_{m^{\prime}})$
$\displaystyle=q_{n}\text{ for each $m^{\prime}\in\\{i_{n-d},\dots,m-1\\}$}$
$\displaystyle\delta_{w}^{\prime}(q_{0},\sigma_{1}\dots\sigma_{m})$
$\displaystyle=q_{d}.$

######  Proof A.9.

Let $m\in\mathbb{N}$ and $w=\sigma_{1}\dots\sigma_{m}\in\Sigma^{m}$ be as
required. Let $l,S,T,I=\\{i_{1},\dots,i_{n-d}\\}$ be as defined above.

We consider (i). We have
$|\mathcal{A}_{w}^{\prime}|=n+1<n+2=\text{ind}(\mathcal{A})$. It remains to
show that
$\mathcal{L}(\mathcal{A})\subseteq\mathcal{L}(\mathcal{A}_{w}^{\prime})$. Let
$w^{\prime}\in\Sigma^{*}$ with
$w^{\prime}\notin\mathcal{L}(\mathcal{A}_{w}^{\prime})$. Since $q_{d}$ is the
only rejecting state of $\mathcal{A}_{w}^{\prime}$, we have
$\delta_{w}^{\prime}(q_{0},w^{\prime})=q_{d}$. Note that
$\mathcal{A}_{w}^{\prime}$ simulates the behavior of $\mathcal{A}$ for the
states $q_{0},\dots,q_{d-1}$ and advances exactly one state at a time for the
states $q_{d},\dots,q_{n}$. This clearly implies that either
$\delta(q_{0},w^{\prime})=q_{d}$ or $\delta(q_{0},w^{\prime})=q_{n+1}$ holds.
Therefore, have $w^{\prime}\notin\mathcal{L}(\mathcal{A})$. We are done with
(i).

Next, we consider (ii). Since
$\sigma_{1}\dots\sigma_{n}\in\mathcal{L}(\mathcal{A})$, we have
$\delta_{w}^{\prime}(q_{0},\sigma_{1}\dots\sigma_{d})=q_{d}$. From here on,
the transitions are chosen in such a way that $\mathcal{A}_{w}^{\prime}$
advances for every occurrence of $\sigma_{m}$ and the first $n-d-l$
occurrences of letters other than $\sigma_{m}$. This guarantees
$\delta_{w}^{\prime}(q_{0},\sigma_{1}\dots\sigma_{i_{n-d}})=q_{n}$. Since
$|\sigma_{i_{n-d}+1}\dots\sigma_{m}|_{\sigma_{m}}=1=|\sigma_{m}|_{\sigma_{m}}$,
the state $q_{n}$ is only left when reading the final letter of $w$. That is,
$\delta_{w}^{\prime}(q_{0},\sigma_{1}\dots\sigma_{m-1})=q_{n}$ and
$\delta_{w}^{\prime}(q_{0},\sigma_{1}\dots\sigma_{m})=q_{d}$. Thus, we have
$w\notin\mathcal{L}(\mathcal{A}_{w}^{\prime})$. We are done with (ii). The
proof of Lemma A.8 is complete.

Note that the construction of Lemma A.8 critically hinges on the property
$|\sigma_{d+1}\dots\sigma_{m}|_{\sigma_{m}}\leq n-d$, which allows to advance
for every occurrence of $\sigma_{m}$ in $\sigma_{d+1}\dots\sigma_{m-1}$. If
$|\sigma_{d+1}\dots\sigma_{m}|_{\sigma_{m}}>n-d$ such a simple construction is
not possible because state $q_{n}$ would be reached with more than one
$\sigma_{m}$ left to read. We will handle words with
$|\sigma_{d+1}\dots\sigma_{m}|_{\sigma_{m}}>n-d$ with different construction,
starting with:

######  Lemma A.10.

Let $m\in\mathbb{N}$ with $n<m\leq n+(n-2)$. Let
$w=\sigma_{1}\dots\sigma_{m}\in\Sigma^{m}$ such that the following conditions
hold:

  1. 1.

$|\sigma_{d+1}\dots\sigma_{m}|_{\sigma_{m}}>n-d$.

  2. 2.

$\forall v\in\Sigma^{n}.v\notin\mathcal{L}(\mathcal{A})\Rightarrow
w\in\mathcal{L}(\mathcal{A}_{v}^{!})$. Note that this implies that every
subsequence of $w$ of length $n$ is in $\mathcal{L}(\mathcal{A})$.

  3. 3.

$\sigma_{n+1}\neq\sigma_{m}$. Note that this implies $m\geq n+2$. Thus, we
have $n+2\leq m\leq n+(n-2)$. This further implies $n\geq 4$.

We define
$\mathcal{A}_{w}^{\prime\prime}=(Q_{w}^{\prime\prime},\Sigma,q_{0},\delta_{w}^{\prime\prime},F_{w}^{\prime\prime})$
as follows:

$\displaystyle Q_{w}^{\prime\prime}$ $\displaystyle=\\{q_{0},\dots,q_{n}\\}$
$\displaystyle F_{w}^{\prime\prime}$
$\displaystyle=Q_{w}^{\prime\prime}\setminus\\{q_{d}\\}$
$\displaystyle\delta_{w}^{\prime\prime}(q_{i},\sigma)$
$\displaystyle=\begin{cases}\delta(q_{i},\sigma)&\text{ if $i<n$ and
$\delta(q_{i},\sigma)\neq q_{n+1}$}\\\ q_{i}&\text{ if $i<n$ and
$\delta(q_{i},\sigma)=q_{n+1}$}\\\ &\text{ (arbitrary definition possible)}\\\
q_{n-[(m-1)-(n+2)+1]}&\text{ if $i=n$ and $\sigma=\sigma_{n+1}$}\\\
q_{d}&\text{ if $i=n$ and $\sigma=\sigma_{m}$}\\\ q_{n}&\text{ else, thus if
$i=n$ and $\sigma\notin\\{\sigma_{n+1},\sigma_{m}\\}$}\\\ &\text{ (arbitrary
definition possible)}\end{cases}.$

Note that $|\sigma_{n+2}\dots\sigma_{m-1}|=(m-1)-(n+2)+1$ holds.

Then the following assertions hold:

$\mathcal{A}_{w}^{\prime\prime}\in\alpha(\mathcal{A})$.

$w\notin\mathcal{L}(\mathcal{A}_{w}^{\prime\prime})$. Making (ii) more
specific, the following holds:

$\displaystyle\delta_{w}^{\prime\prime}(q_{0},\sigma_{1}\dots\sigma_{n})$
$\displaystyle=q_{n}$
$\displaystyle\delta_{w}^{\prime\prime}(q_{0},\sigma_{1}\dots\sigma_{n+1})$
$\displaystyle=q_{n-[(m-1)-(n+2)+1]}$
$\displaystyle\delta_{w}^{\prime\prime}(q_{0},\sigma_{1}\dots\sigma_{m^{\prime}})$
$\displaystyle=q_{n-[(m-1)-(n+2)+1]+(m^{\prime}-(n+1))}\text{ for each
$m^{\prime}\in\\{n+2,\dots,m-1\\}$}$
$\displaystyle\delta_{w}^{\prime\prime}(q_{0},\sigma_{1}\dots\sigma_{m})$
$\displaystyle=q_{d}.$

######  Proof A.11.

Let $m\in\mathbb{N}$ and $w=\sigma_{1}\dots\sigma_{m}\in\Sigma^{m}$ be as
required.

We begin by showing that $\mathcal{A}_{w}^{\prime\prime}$ is well-defined.
That is, we show that $n-[(m-1)-(n+2)+1]\in\\{0,\dots,n\\}$. Note that
$n-[(m-1)-(n+2)+1]=2n+2-m$. Since $n+2\leq m\leq n+(n-2)$, we have
$n-[(m-1)-(n+2)+1]=2n+2-m\geq 2n+2-(n+(n-2))=4$ and
$n-[(m-1)-(n+2)+1]=2n+2-m\leq 2n+2-(n+2)=n$. Thus, we have $4\leq
n-[(m-1)-(n+2)+1]\leq n$. Since $n\geq 4$, this implies that
$\mathcal{A}_{w}^{\prime\prime}$ is well-defined.

Next, we turn to (i). We argue that
$\mathcal{A}_{w}^{\prime\prime}\in\alpha(\mathcal{A})$. The argumentation here
is similar to Lemma A.8 (i). We have
$|\mathcal{A}_{w}^{\prime\prime}|=n+1<n+2=\text{ind}(\mathcal{A})$.
Additionally, for a word $w^{\prime}\in\Sigma^{*}$ we have
$\delta_{w}^{\prime\prime}(q_{0},w^{\prime})=q_{d}$ only if
$\delta(q_{0},w^{\prime})=q_{d}$ or $\delta(q_{0},w^{\prime})=q_{n+1}$, which
implies
$\mathcal{L}(\mathcal{A})\subseteq\mathcal{L}(\mathcal{A}_{w}^{\prime\prime})$.
Thus, we have $\mathcal{A}_{w}^{\prime\prime}\in\alpha(\mathcal{A})$.

Finally, we turn to (ii).

The crucial observation is that, since every subsequence of $w$ of length $n$
is in $\mathcal{L}(\mathcal{A})$, the subsequences $\sigma_{1}\dots\sigma_{n}$
and $\sigma_{1}\dots\sigma_{n-[(m-1)-(n+2)+1]}\sigma_{n+2}\dots\sigma_{m-1}$
are in $\mathcal{L}(\mathcal{A})$.

This implies
$\sigma_{w}^{\prime\prime}(q_{0},\sigma_{1}\dots\sigma_{n})=q_{n}$ and
$\delta_{w}^{\prime\prime}(q_{n-[(m-1)-(n+2)+1]},\sigma_{n+2}\dots\sigma_{m-1})=q_{n}$,
which implies $\delta_{w}^{\prime\prime}(q_{0},w)=q_{d}$. We are done with
(ii). The proof of Lemma A.10 is complete.

Note that the construction of Lemma A.10 critically hinges on the property
$\sigma_{n+1}\neq\sigma_{m}$. This allows to circle back to different states
when reaching $q_{n}$ after reading $\sigma_{1}\dots\sigma_{n}$ and
$\sigma_{1}\dots\sigma_{m-1}$. If $\sigma_{n+1}=\sigma_{m}$ this construction
is not possible. Therefore, we still have to handle words
$w=\sigma_{1}\dots\sigma_{m}\in\Sigma_{m}$ with $n<m\leq n+(n-2)$,
$|\sigma_{d+1}\dots\sigma_{m}|_{\sigma_{m}}>n-d$ and $\sigma_{n+1}=\sigma_{m}$
for which every subsequence of length $n$ is in $\mathcal{L}(\mathcal{A})$. As
mentioned in Section 3.1, we will differentiate between two more cases, thus
introducing two further lemmas.

We begin with:

######  Lemma A.12.

Let $m\in\mathbb{N}$ with $n<m\leq n+(n-2)$. Let
$w=\sigma_{1}\dots\sigma_{m}\in\Sigma^{m}$ such that the following conditions
hold:

  1. 1.

$|\sigma_{d+1}\dots\sigma_{m}|_{\sigma_{m}}>n-d$.

  2. 2.

$\forall v\in\Sigma^{n}.v\notin\mathcal{L}(\mathcal{A})\Rightarrow
w\in\mathcal{L}(\mathcal{A}_{v}^{!})$. Note that this implies that every
subsequence of $w$ of length $n$ is in $\mathcal{L}(\mathcal{A})$.

  3. 3.

$\sigma_{n+1}=\sigma_{m}$.

  4. 4.

Let $x\in\mathbb{N}_{\geq 1}$ and $u\in\Sigma^{*}$ with $u\neq v\sigma_{m}$
for each $v\in\Sigma^{*}$ such that
$w=\sigma_{1}\dots\sigma_{d}u\sigma_{m}^{x}$. Let $b\in\\{0,1\\}$ with $b=1$
if $\sigma_{d+1}\neq\sigma_{m}$ and $b=0$ otherwise. Then
$|u|_{\sigma_{m}}=|\sigma_{d+1}\dots\sigma_{m-x}|_{\sigma_{m}}<n-d-b$ holds.

Let $l=|\sigma_{d+1}\dots\sigma_{m}|_{\sigma_{m}}$.

We define
$\mathcal{A}_{w}^{\prime\prime\prime}=(Q_{w}^{\prime\prime\prime},\Sigma,q_{0},\delta_{w}^{\prime\prime\prime},F_{w}^{\prime\prime\prime})$
as follows:

$\displaystyle Q_{w}^{\prime\prime\prime}$
$\displaystyle=\\{q_{0},\dots,q_{n}\\}$ $\displaystyle
F_{w}^{\prime\prime\prime}$
$\displaystyle=Q_{w}^{\prime\prime\prime}\setminus\\{q_{d}\\}$
$\displaystyle\delta_{w}^{\prime\prime\prime}(q_{i},\sigma)$
$\displaystyle=\begin{cases}\delta(q_{i},\sigma)&\text{ if $i<d$ and
$\delta(q_{i},\sigma)\neq q_{n+1}$}\\\ q_{i}&\text{ if $i<d$ and
$\delta(q_{i},\sigma)=q_{n+1}$}\\\ &\text{ (arbitrary definition possible)}\\\
q_{d+1}&\text{ if $i=d$}\\\ q_{i+1}&\text{ if $d<i<n-1$ and
$\sigma=\sigma_{m}$}\\\ q_{i}&\text{ if $d<i<n-1$ and
$\sigma\neq\sigma_{m}$}\\\ q_{d-[x-(n-(d+b+(l-x))+1)]}&\text{ if $i=n$ and
$\sigma=\sigma_{m}$}\\\ q_{n}&\text{ else, thus if $i=n$ and
$\sigma\neq\sigma_{m}$}\end{cases}.$

Then the following assertions hold:

$\mathcal{A}_{w}^{\prime\prime\prime}\in\alpha(\mathcal{A})$.

$w\notin\mathcal{L}(\mathcal{A}_{w}^{\prime\prime\prime})$. Making (ii) more
specific, the following holds:

$\displaystyle\delta_{w}^{\prime\prime\prime}(q_{0},\sigma_{1}\dots\sigma_{d})$
$\displaystyle=q_{d}$
$\displaystyle\delta_{w}^{\prime\prime\prime}(q_{0},\sigma_{1}\dots\sigma_{d+1})$
$\displaystyle=q_{d+1}$
$\displaystyle\delta_{w}^{\prime\prime\prime}(q_{0},\sigma_{1}\dots\sigma_{m-x})$
$\displaystyle=q_{d+b+(l-x)}$
$\displaystyle\delta_{w}^{\prime\prime\prime}(q_{0},\sigma_{1}\dots\sigma_{m-x}\sigma_{m}^{n-(d+b+(l-x))})$
$\displaystyle=q_{n}$
$\displaystyle\delta_{w}^{\prime\prime\prime}(q_{0},\sigma_{1}\dots\sigma_{m-x}\sigma_{m}^{n-(d+b+(l-x))}\sigma_{m})$
$\displaystyle=q_{d-[x-(n-(d+b+(l-x))+1)]}$
$\displaystyle\delta_{w}^{\prime\prime\prime}(q_{0},\sigma_{1}\dots\sigma_{m})$
$\displaystyle=q_{d}.$

######  Proof A.13.

Let $m\in\mathbb{N}$ and $w=\sigma_{1}\dots\sigma_{m}\in\Sigma^{m}$ be as
required. Let $l,u,x,b$ be as defined above.

Again we begin by showing that $\mathcal{A}_{w}^{\prime\prime\prime}$ is well
defined. That is, we show that $d-[x-(n-(d+b+(l-x))+1)]\in\\{0,\dots,n\\}$.
Note that $d-[x-(n-(d+b+(l-x))+1)]=n-l-b+1$.

On the one hand, since $w\in\mathcal{L}(\mathcal{A}_{\sigma_{m}^{n}}^{!})$
holds, we have
$l=|\sigma_{d+1}\dots\sigma_{m}|_{\sigma_{m}}\leq|w|_{\sigma_{m}}\leq n-1$. We
further have $b\leq 1$. Therefore, we have
$d-[x-(n-(d+b+(l-x))+1)]=n-l-b+1\geq n-(n-1)-(1)+1=1$. On the other hand, we
have $l>n-d$ and $b\geq 0$. Therefore, we have
$d-[x-(n-(d+b+(l-x))+1)]=n-l-b+1\leq n-(n-d+1)-(0)+1=d<n$. Taken together we
have $1\leq d-[x-(n-(d+b+(l-x))+1)]\leq d<n$.

First, note that per definition $n<n+(n-2)$ holds, which implies $2<n$.
Second, note that per definition
$|\sigma_{d+1}\dots\sigma_{m}|_{\sigma_{m}}>n-d$ holds and, again, that we
have $|\sigma_{d+1}\dots\sigma_{m}|_{\sigma_{m}}\leq n-1$. This implies
$n-1>n-d$ and thus $d>1$.

Therefore, we have $1\leq d-[x-(n-(d+b+(l-x))+1)]\leq d<n$ and $1<d$. The DFA
$\mathcal{A}_{w}^{\prime\prime\prime}$ is well-defined.

Next, we turn to (i). Again, we refer to Lemma A.8. We have
$|\mathcal{A}_{w}^{\prime\prime\prime}|=n+1<n+2=\text{ind}(\mathcal{A})$ and
for each $w^{\prime}\in\Sigma^{*}$ we have
$\delta_{w}^{\prime\prime\prime}(q_{0},w^{\prime})=q_{d}$ only if
$\delta(q_{0},w^{\prime})=q_{d}$ or $\delta(q_{0},w^{\prime})=q_{n+1}$, which
implies $w^{\prime}\notin\mathcal{L}(\mathcal{A})$. Therefore, we have
$\mathcal{A}_{w}^{\prime\prime\prime}\in\alpha(\mathcal{A})$.

Finally, we turn to (ii).

Clearly, we have
$\delta_{w}^{\prime\prime\prime}(q_{0},\sigma_{1}\dots\sigma_{d})=q_{d}$ and
$\delta_{w}^{\prime\prime\prime}(q_{0},\sigma_{1}\dots\sigma_{d+1})=q_{d+1}$.
Note that the first occurrence of a $\sigma_{m}$ in the subword
$\sigma_{d+1}\dots\sigma_{m}$ is read in $q_{d+b}$. Note further that with
$l>n-d$ there exist enough occurrences of $\sigma_{m}$ in
$\sigma_{d+1}\dots\sigma_{m}$ to reach $q_{n}$ and afterwards
$q_{d-[x-(n-(d+b+(l-x))+1)]}$. Also, by definition we have
$l-x=|u|_{\sigma_{m}}<n-d-b$ and therefore $d+b+(l-x)<n$. This implies that
$q_{n}$ is reached only after subword $u$ is read completely. Thus, we have
$\delta_{w}^{\prime\prime\prime}(q_{0},\sigma_{1}\dots\sigma_{d}u)=q_{d+b+(l-x)}$.
To then reach $q_{n}$, the subword $\sigma_{m}^{n-(d+b+(l-x))}$ has to be
read. Therefore, we have
$\delta_{w}^{\prime\prime\prime}(q_{0},\sigma_{1}\dots\sigma_{d}u\sigma_{m}^{n-(d+b+(l-x))})=q_{n}$
and
$\delta_{w}^{\prime\prime\prime}(q_{0},\sigma_{1}\dots\sigma_{d}u\sigma_{m}^{n-(d+b+(l-x))+1})=q_{d-[x-(n-(d+b+(l-x))+1)]}$.

After this, only the suffix $\sigma_{m}^{x-(n-(d+b+(l-x))+1)}$ remains, while
the DFA is in the state $q_{d-[x-(n-(d+b+(l-x))+1)]}$.

Now we only need to show that
$\delta_{w}^{\prime\prime\prime}(q_{d-[x-(n-(d+b+(l-x))+1)]},\sigma_{m}^{x-(n-(d+b+(l-x))+1)})=q_{d}$
holds. It is sufficient to proof the following: $\forall
i\in\\{d-[x-(n-(d+b+(l-x))+1)]+1,\dots,d\\}.\sigma_{m}\in\Sigma_{i-1,i}$.

Note that $\sigma_{1}\dots\sigma_{d}\sigma_{m}^{l}$ with $l>n-d$ is a
subsequence of $w$. This implies that
$v=\sigma_{1}\dots\sigma_{n-l}\sigma_{m}^{l}$ is a subsequence of $w$. Note
that $|v|=n$. Therefore, we have $v\in\mathcal{L}(\mathcal{A})$. This implies:
$\forall i\in\\{n-l+1,\dots,n\\}.\sigma_{m}\in\Sigma_{i-1,i}$.

Now note that $b\leq 1$ implies $d-[x-(n-(d+b+(l-x))+1)]+1=n-l-b+1+1\geq
n-l+1$. Therefore, we have: $\forall
i\in\\{d-[x-(n-(d+b+(l-x))+1)]+1,\dots,d\\}.\sigma_{m}\in\Sigma_{i-1,i}$.

As argued above, this implies
$\delta_{w}^{\prime\prime\prime}(q_{d-[x-(n-(d+b+(l-x))+1)]},\sigma_{m}^{x-(n-(d+b+(l-x))+1)})=q_{d}$
and therefore $\delta_{w}^{\prime\prime\prime}(q_{0},w)=q_{d}$. We are done
with (ii). The proof of Lemma A.12 is complete.

Finally, we introduce:

######  Lemma A.14.

Let $m\in\mathbb{N}$ with $n<m\leq n+(n-2)$. Let
$w=\sigma_{1}\dots\sigma_{m}\in\Sigma^{m}$ such that the following conditions
hold:

  1. 1.

$|\sigma_{d+1}\dots\sigma_{m}|_{\sigma_{m}}>n-d$.

  2. 2.

$\forall v\in\Sigma^{n}.v\notin\mathcal{L}(\mathcal{A})\Rightarrow
w\in\mathcal{L}(\mathcal{A}_{v}^{!})$. Note that this implies that every
subsequence of $w$ of length $n$ is in $\mathcal{L}(\mathcal{A})$.

  3. 3.

$\sigma_{n+1}=\sigma_{m}$.

  4. 4.

Let $x\in\mathbb{N}_{\geq 1}$ and $u\in\Sigma^{*}$ with $u\neq v\sigma_{m}$
for each $v\in\Sigma^{*}$ such that
$w=\sigma_{1}\dots\sigma_{d}u\sigma_{m}^{x}$. Let $b\in\\{0,1\\}$ with $b=1$
if $\sigma_{d+1}\neq\sigma_{m}$ and $b=0$ otherwise. Then
$|u|_{\sigma_{m}}=|\sigma_{d+1}\dots\sigma_{m-x}|_{\sigma_{m}}\geq n-d-b$
holds.

  5. 5.

Let $i\in\\{1,\dots,n\\}$ be the maximal value with
$\sigma_{m}\notin\Sigma_{i-1,i}$. Then
$w\notin\mathcal{L}(\mathcal{A}_{\sigma_{m},i})$ holds.

We define
$\mathcal{A}_{w}^{\prime\prime\prime\prime}=(Q_{w}^{\prime\prime\prime\prime},\Sigma,q_{0},\delta_{w}^{\prime\prime\prime\prime},F_{w}^{\prime\prime\prime\prime})$
as follows:

$\displaystyle Q_{w}^{\prime\prime\prime\prime}$
$\displaystyle=\\{q_{0},\dots,q_{n}\\}$ $\displaystyle
F_{w}^{\prime\prime\prime\prime}$
$\displaystyle=Q_{w}^{\prime\prime\prime\prime}\setminus\\{q_{d}\\}$
$\displaystyle\delta_{w}^{\prime\prime\prime\prime}(q_{i},\sigma)$
$\displaystyle=\begin{cases}\delta(q_{i},\sigma)&\text{ if $i<n$ and
$\delta(q_{i},\sigma)\neq q_{n+1}$}\\\ q_{i}&\text{ if $i<n$ and
$\delta(q_{i},\sigma)=q_{n+1}$}\\\ &\text{ (arbitrary definition possible)}\\\
q_{n-[(m-x-1)-(n+2)+1]}&\text{ if $i=n$ and $\sigma=\sigma_{m}$}\\\
q_{d-x}&\text{ if $i=n$ and $\sigma=\sigma_{m-x}$}\\\ q_{n}&\text{ else, thus
if $i=n$ and $\sigma\notin\\{\sigma_{m},\sigma_{m-x}$\\}}\\\ &\text{
(arbitrary definition possible)}\end{cases}.$

Then the following assertions hold:

$\mathcal{A}_{w}^{\prime\prime\prime\prime}\in\alpha(\mathcal{A})$.

$w\notin\mathcal{L}(\mathcal{A}_{w}^{\prime\prime\prime\prime})$. Making (ii)
more specific, the following holds:

$\displaystyle\delta_{w}^{\prime\prime\prime\prime}(q_{0},\sigma_{1}\dots\sigma_{n})$
$\displaystyle=q_{n}$
$\displaystyle\delta_{w}^{\prime\prime\prime\prime}(q_{0},\sigma_{1}\dots\sigma_{n+1})$
$\displaystyle=q_{n-[(m-x-1)-(n+2)+1]}$
$\displaystyle\delta_{w}^{\prime\prime\prime\prime}(q_{0},\sigma_{1}\dots\sigma_{m^{\prime}})$
$\displaystyle=q_{n-[(m-x-1)-(n+2)+1]+(m^{\prime}-(n+1))}$ for each
$m^{\prime}\in\\{n+2,\dots,m-x-1\\}$
$\displaystyle\delta_{w}^{\prime\prime\prime\prime}(q_{0},\sigma_{1}\dots\sigma_{m-x})$
$\displaystyle=q_{d-x}$
$\displaystyle\delta_{w}^{\prime\prime\prime\prime}(q_{0},\sigma_{1}\dots\sigma_{m})$
$\displaystyle=q_{d}.$

######  Proof A.15.

Let $m\in\mathbb{N}$ and $w=\sigma_{1}\dots\sigma_{m}\in\Sigma^{m}$ be as
required. Let $u,x,b$ be as defined above. Define
$l=|\sigma_{d+1}\dots\sigma_{m}|_{\sigma_{m}}$.

Again, we show that $\mathcal{A}_{w}^{\prime\prime\prime\prime}$ is well-
defined. That is, we show that $n-[(m-x-1)-(n+2)+1],d-x\in\\{0,\dots,n\\}$.

We begin by showing $n-[(m-x-1)-(n+2)+1]\in\\{0,\dots,n\\}$. Note that with
$w=\sigma_{1}\dots\sigma_{d}u\sigma_{m}^{x}$ we have $1\leq x\leq m-d$, which
implies $d\leq m-x\leq m-1$.

To show that $n-[(m-x-1)-(n+2)+1]\in\\{0,\dots,n\\}$ we prove $m-x\geq n+2$ by
contradiction. Assume $m-x<n+2$.

Case 1: $m-x=d$.

Then $w=\sigma_{1}\dots\sigma_{d}\sigma_{m}^{x}$ holds. Since
$\sigma_{d+1}=\sigma_{m}$, we have $b=0$. This implies
$|u|_{\sigma_{m}}=0<1=n-(n-1)\leq n-d=n-d-b$, but $|u|_{\sigma_{m}}<n-d-b$ is
a contradiction to the condition $|u|_{\sigma_{m}}\geq n-d-b$. We are done
with Case 1.

Case 2: $m-x>d$.

Then $d<m-x<n+2$ holds. Because of $\sigma_{m-x}\neq\sigma_{m}=\sigma_{n+1}$
we have $m-x\neq n+1$ and therefore $d<m-x<n+1$. This implies:

$\displaystyle|u|_{\sigma_{m}}$
$\displaystyle=|\sigma_{d+1}\dots\sigma_{m-x}|_{\sigma_{m}}$
$\displaystyle=(1-b)+|\sigma_{d+2}\dots\sigma_{m-x}|_{\sigma_{m}}$
$\displaystyle=(1-b)+|\sigma_{d+2}\dots\sigma_{m-x-1}|_{\sigma_{m}}$
$\displaystyle\leq(1-b)+|\sigma_{d+2}\dots\sigma_{m-x-1}|$
$\displaystyle=(1-b)+(m-x-1)-(d+2)+1$ $\displaystyle=(m-x)-b-d-1$
$\displaystyle<(m-x)-b-d$ $\displaystyle\leq n-b-d.$

Again, $|u|_{\sigma_{m}}<n-d-b$ is a contradiction to the condition
$|u|_{\sigma_{m}}\geq n-d-b$. We are done with Case 2.

With Cases 1 and 2 we have shown $m-x\geq n+2$ by contradiction. This means
that the last occurrence of a letter unequal to $\sigma_{m}$ in $w$ is in the
subword $\sigma_{n+2}\dots\sigma_{m-x}$.

Now we return to our proof of $n-[(m-x-1)-(n+2)+1]\in\\{0,\dots,n\\}$. Since
$m-x\geq n+2$, we have $n-[(m-x-1)-(n+2)+1]=2n+2-(m-x)\leq 2n+2-(n+2)=n$.
Additionally, since $m\leq n+(n-2)$, we have
$n-[(m-x-1)-(n+2)+1]=2n+2-(m-x)\geq 2n+2-(n+(n-2))+x=x+4$. Taken together we
have $x+4\leq n-[(m-x-1)-(n+2)+1]\leq n$.

Note that $m-x\geq n+2$ and $m\leq n+(n-2)$, which implies $n+2+x\leq n+(n-2)$
and therefore $x+4\leq n$. We have proven
$n-[(m-x-1)-(n+2)+1]\in\\{0,\dots,n\\}$.

Now we proof $d-x\in\\{0,\dots,n\\}$. Note that
$l=|\sigma_{d+1}\dots\sigma_{m}|_{\sigma_{m}}=|u\sigma_{m}^{x}|_{\sigma_{m}}=|u|_{\sigma_{m}}+x$
and therefore $x=l-|u|_{\sigma_{m}}$. Additionally, because of
$w\in\mathcal{L}(\mathcal{A}_{\sigma_{m}^{n}}^{!})$ we have $l\leq n-1$.
Finally, per requirement $|u|_{\sigma_{m}}\geq n-d-b$ holds. Taken together we
have:

$\displaystyle x$ $\displaystyle=l-|u|_{\sigma_{m}}$
$\displaystyle\leq(n-1)-(n-d-b)$ $\displaystyle=d+b-1$ $\displaystyle\leq
d+1-1$ $\displaystyle=d.$

This implies $d-x\geq d-d=0$.

Further, because of $d\leq n-1$ and $x\geq 1$ we have $d-x\leq(n-1)-1=n-2$.

Taken together we have $0\leq d-x\leq n-2$. Again, note that $n<m\leq n+(n-2)$
implies $2<n$. We have proven $d-x\in\\{0,\dots,n\\}$.

With $n-[(m-x-1)-(n+2)+1],d-x\in\\{0,\dots,n\\}$ the DFA
$\mathcal{A}_{w}^{\prime\prime\prime\prime}$ is well-defined.

Next, we consider (i). The proof of
$\mathcal{A}_{w}^{\prime\prime\prime\prime}\in\alpha(\mathcal{A})$ is again
similar to Lemma A.8, since
$|\mathcal{A}_{w}^{\prime\prime\prime\prime}|=n+1<n+2=\text{ind}(\mathcal{A})$
holds and for each $w^{\prime}\in\Sigma^{*}$ we have
$\delta_{w}^{\prime\prime\prime\prime}(q_{0},w^{\prime})=q_{d}$ only if
$\delta(q_{0},w^{\prime})=q_{d}$ or $\delta(q_{0},w^{\prime})=q_{n+1}$.

Finally, we look at (ii). Obviously, we have
$\delta_{w}^{\prime\prime\prime\prime}(q_{0},\sigma_{1}\dots\sigma_{n})=q_{n}$
and
$\delta_{w}^{\prime\prime\prime\prime}(q_{0},\sigma_{1}\dots\sigma_{n+1})=q_{n-[(m-x-1)-(n+2)+1]}$.

Now note that
$v=\sigma_{1}\dots\sigma_{n-[(m-x-1)-(n+2)+1]}\sigma_{n+2}\dots\sigma_{m-x-1}$
is a subsequence of $w$ with $|v|=n$. This implies
$v\in\mathcal{L}(\mathcal{A})$ and therefore
$\delta_{w}^{\prime\prime\prime\prime}(q_{n-[(m-x-1)-(n+2)+1]},\sigma_{n+2}\dots\sigma_{m-x-1})=q_{n}$.
Therefore, we have
$\delta_{w}^{\prime\prime\prime\prime}(q_{0},\sigma_{1}\dots\sigma_{m-x-1})=q_{n}$
and
$\delta_{w}^{\prime\prime\prime\prime}(q_{0},\sigma_{1}\dots\sigma_{m-x})=q_{d-x}$.

After reading $\sigma_{1}\dots\sigma_{m-x}$, only the suffix $\sigma_{m}^{x}$
is left to be read and we have to show that
$\delta_{w}^{\prime\prime\prime\prime}(q_{d-x},\sigma_{m}^{x})=d$. It is
sufficient to prove: $\forall
j\in\\{d-x+1,\dots,d\\}.\sigma_{m}\in\Sigma_{j-1,j}$.

Let $i\in\\{1,\dots,n\\}$ be the largest value with
$\sigma_{m}\notin\Sigma_{i-1,i}$. We have to show that $i<d-x+1$. To do so we
consider the DFA $\mathcal{A}_{\sigma_{m},i}$. Per requirement
$w\in\mathcal{L}(\mathcal{A}_{\sigma_{m},i})$ holds.

Again, we use that $\sigma_{1}\dots\sigma_{d}\sigma_{m}^{l}$ with $l>n-d$ is a
subsequence of $w$, which implies that
$v=\sigma_{1}\dots\sigma_{n-l}\sigma_{m}^{l}$ is a subsequence of $w$ with
$|v|=n$. Therefore, we have $v\in\mathcal{L}(\mathcal{A})$. This implies:
$\forall j\in\\{n-l+1,\dots,n\\}.\sigma_{m}\in\Sigma_{j-1,j}$. It follows that
$i<n-l+1$ and thus $i-1<n-l$.

Now note that $l>n-d$ and $n-l>i-1$ implies $d>n-l>i-1$. This immediately
implies $\delta_{\sigma_{m},i}(q_{0},\sigma_{1}\dots\sigma_{d})=q_{j}$ for
some $j\in\\{0,\dots,n\\},j\geq i-1$.

Next, let $t\in\\{d+1,\dots,m\\}$ be the smallest value such that
$\sigma_{t}=\sigma_{m}$. Since $\sigma_{n+1}=\sigma_{m}$, we have $t\leq n+1$.
Since $m-x\geq n+2$, we additionally have $t<m-x$.

Since $\delta_{\sigma_{m},i}(q_{0},\sigma_{1}\dots\sigma_{d})=q_{j}$ for some
$j\in\\{0,\dots,n\\},j\geq i-1$ and
$w\in\mathcal{L}(\mathcal{A}_{\sigma_{m},i})$, after the first occurrence of
$\sigma_{m}$ in $\sigma_{d+1}\dots\sigma_{m}$ there can only be
$(n-1)-(j+1)\leq(n-1)-i$ additional letters. That is:
$|\sigma_{t}\dots\sigma_{m}|\leq(n-1)-j\leq(n-1)-(i-1)=n-i$.

This implies:

$\displaystyle l$ $\displaystyle=|\sigma_{d+1}\dots\sigma_{m}|_{\sigma_{m}}$
$\displaystyle=|\sigma_{t}\dots\sigma_{m}|_{\sigma_{m}}$
$\displaystyle=|\sigma_{t}\dots\sigma_{m-x-1}\sigma_{m-x}\sigma_{m-x+1}\dots\sigma_{m}|_{\sigma_{m}}$
$\displaystyle=|\sigma_{t}\dots\sigma_{m-x-1}\sigma_{m-x+1}\dots\sigma_{m}|_{\sigma_{m}}$
$\displaystyle\leq|\sigma_{t}\dots\sigma_{m-x-1}\sigma_{m-x+1}\dots\sigma_{m}|$
$\displaystyle=|\sigma_{t}\dots\sigma_{m}|-1$ $\displaystyle\leq(n-i)-1.$

With $x=l-|u|_{\sigma_{m}}$ and $l\leq n-i-1$ and $|u|_{\sigma_{m}}\geq n-d-b$
we get:

$\displaystyle x$ $\displaystyle=l-|u|_{\sigma_{m}}$
$\displaystyle\leq(n-i-1)-(n-d-b)$ $\displaystyle=d+b-i-1$ $\displaystyle\leq
d+1-i-1$ $\displaystyle=d-i.$

Thus, we have $1\leq x\leq d-i$. Note that with $i-1<n-l<d$, which implies
$i\leq d-1$, we indeed have $1\leq d-i$.

In conclusion, we have $x\leq d-i$ and therefore $i\leq d-x<d-x+1$, which
implies: $\forall j\in\\{d-x+1,\dots,d\\}.\sigma_{m}\in\Sigma_{j-1,j}$. This
implies $\delta_{w}^{\prime\prime\prime\prime}(q_{d-x},\sigma_{m}^{x})=q_{d}$
and thus $\delta_{w}^{\prime\prime\prime\prime}(q_{0},w)=q_{d}$. We are done
with (ii). The proof of Lemma A.14 is complete.

Note that the case distinction in Lemmas A.12 and A.14 is found in the fourth
condition. That is, $|u|_{\sigma_{m}}<n-d-b$ and $|u|_{\sigma_{m}}\geq n-d-b$.
The fifth condition in Lemma A.14 uses the fact that our decomposition
contains the DFAs of the form $\mathcal{A}_{\sigma,i}$. This allows us to
restrict the construction of DFAs $\tilde{\mathcal{A}}_{w}$ in general to
words $w$ which are not rejected by the DFAs of the form
$\mathcal{A}_{\sigma,i}$. This can be seen in Lemma 3.5, which explicitly
states this condition. But since we only need this condition in Lemma A.14,
while for Lemmas A.8, A.10 and A.12 it is enough to require $|w|\leq n+(n-2)$,
we only state this requirement in Lemma A.14.

Note further that we indeed need the two lemmas, Lemmas A.12 and A.14.

The construction in Lemma A.12 does not work for words with
$|u|_{\sigma_{m}}\geq n-d-b$, since after arriving in $q_{n}$ and circling
back to $q_{d-[x-(n-(d+b+(l-x))+1)]}$, the remaining suffix is not necessarily
of the form $\sigma_{m}^{k}$ for $k\in\mathbb{N}$. This is problematic, since
we cannot guarantee that for the remaining letters $\sigma\neq\sigma_{m}$ the
DFA $\mathcal{A}_{w}^{\prime\prime\prime}$ advances exactly one state.
Additionally, we cannot even be certain how many letters are left to be read.

The construction in Lemma A.14 does not work for words with
$|u|_{\sigma_{m}}<n-d-b$, since after arriving in $q_{n}$ for the second time
and circling back to $q_{d-x}$, we cannot use the subsequence argument to
ensure that $\sigma_{m}\in\Sigma_{j-1,j}$ for each $j\in\\{d-x+1,d\\}$. In
other words, it is possible that not enough occurences of the letter
$\sigma_{m}$ were read before $\mathcal{A}_{w}^{\prime\prime\prime\prime}$
circles back to $q_{d-x}$.

Therefore, we indeed need the case distinction captured by Lemmas A.12 and
A.14.

With Lemmas A.8, A.10, A.12 and A.14 in hand, the proof of Lemma 3.5 is
obvious:

######  Proof A.16 (Proof of Lemma 3.5).

Let $w\in\Sigma^{*}$ be as required. That is, $|w|>n$ with
$w\in\mathcal{L}(\mathcal{A}_{v}^{!})$ for each $v\notin L,|v|=n$ and
$w\in\bigcap_{\sigma\in\Sigma}\mathcal{L}(\mathcal{A}_{\sigma,i_{\sigma}})$.
Note that this implies $n<|w|\leq n+(n-2)$.

Then the word $w$ satisfies the conditions of one lemma out of Lemmas A.8,
A.10, A.12 and A.14. Select the respective DFA as $\tilde{\mathcal{A}}_{w}$.
Then DFA $\tilde{\mathcal{A}}_{w}$ witnesses the validity of Lemma 3.5. We are
done.

We have proven Lemmas 3.2, 3.3, 3.4 and 3.5. This leads to a simple proof of 1
(1):

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

We have to show that $\mathcal{A}$ is composite.

We start by defining
$X^{\prime},X^{\prime\prime},X^{\prime\prime\prime},X^{\prime\prime\prime\prime}$
as the sets of words for which the conditions of the respective lemma out of
Lemmas 3.2, 3.3, 3.4 and 3.5 hold. We further define
$X^{!}=\\{w\in\Sigma^{n}\hskip 5.69054pt|\hskip 5.69054ptw\notin L\\}$.
Finally, for each $\sigma\in\Sigma$ we define
$i_{\sigma}=\max(\\{i\in\\{1,\dots,n\\}\hskip 5.69054pt|\hskip
5.69054pt\sigma\notin\Sigma_{i-1,i}\\})$.

We prove:

$\displaystyle L$
$\displaystyle=\mathcal{L}(\mathcal{A}_{0})\cap\mathcal{L}(\hat{\mathcal{A}}_{d})$
$\displaystyle\cap\bigcap_{m=1}^{n-1}\bigcap_{\underline{i}\in
I_{m}}\mathcal{L}(\mathcal{A}_{\underline{i}})\cap\bigcap_{w\in
X^{!}}\mathcal{L}(\mathcal{A}_{w}^{!})\cap\bigcap_{\sigma\in\Sigma}\mathcal{L}(\mathcal{A}_{\sigma,i_{\sigma}})$
$\displaystyle\cap\bigcap_{w\in
X^{\prime}}\mathcal{L}(\mathcal{A}_{w}^{\prime})\cap\bigcap_{w\in
X^{\prime\prime}}\mathcal{L}(\mathcal{A}_{w}^{\prime\prime})\cap\bigcap_{w\in
X^{\prime\prime\prime}}\mathcal{L}(\mathcal{A}_{w}^{\prime\prime\prime})\cap\bigcap_{w\in
X^{\prime\prime\prime\prime}}\mathcal{L}(\mathcal{A}_{w}^{\prime\prime\prime\prime}).$

We denote the language created by the decomposition on the right hand side
with $L_{\cap}$.

Note that with Lemmas 3.2, 3.3, 3.4 and 3.5 each of the DFAs used for the
decomposition is in $\alpha$($\mathcal{A}$). Therefore, they are sufficiently
small and $L\subseteq L_{\cap}$ holds. It remains to show that
$L_{\cap}\subseteq L$.

Let $w\in\Sigma^{*}$ with $w\notin L$. First, assume that:

$\displaystyle w$
$\displaystyle\notin\mathcal{L}(\mathcal{A}_{0})\cap\mathcal{L}(\hat{\mathcal{A}}_{d})$
$\displaystyle\cap\bigcap_{m=1}^{n-1}\bigcap_{\underline{i}\in
I_{m}}\mathcal{L}(\mathcal{A}_{\underline{i}})\cap\bigcap_{w\in
X^{!}}\mathcal{L}(\mathcal{A}_{w}^{!})\cap\bigcap_{\sigma\in\Sigma}\mathcal{L}(\mathcal{A}_{\sigma,i_{\sigma}}).$

Then we are done immediately.

Thus, we assume that $w$ is not rejected by these DFAs. This clearly implies
$w\in X^{\prime}\cup X^{\prime\prime}\cup X^{\prime\prime\prime}\cup
X^{\prime\prime\prime\prime}$. Therefore, we have:

$\displaystyle w\notin\bigcap_{w\in
X^{\prime}}\mathcal{L}(\mathcal{A}_{w}^{\prime})\cap\bigcap_{w\in
X^{\prime\prime}}\mathcal{L}(\mathcal{A}_{w}^{\prime\prime})\cap\bigcap_{w\in
X^{\prime\prime\prime}}\mathcal{L}(\mathcal{A}_{w}^{\prime\prime\prime})\cap\bigcap_{w\in
X^{\prime\prime\prime\prime}}\mathcal{L}(\mathcal{A}_{w}^{\prime\prime\prime\prime}).$

This implies $w\notin L_{\cap}$. We have shown $L_{\cap}\subseteq L$. The
proof of 1 (1) is complete.

To summarize, we have introduced four additional lemmas, Lemmas A.8, A.10,
A.12 and A.14, and using these have proven Lemmas 3.2, 3.3, 3.4 and 3.5. After
this, the proof of 1 (1) was obvious.

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

Next, we consider 1 (1). We still assume that $\mathcal{A}$ is of the form
described at the end of Section A.1. That is, $\mathcal{A}$ is of the form
displayed in Figure 4.

We prove that $\mathcal{A}$ is composite if it has the CEP. That is, if for
every $w\in\mathcal{L}(\mathcal{A})$ with $|w|=n$ there exists a compression
$w^{\prime}$ of $w$ such that every extension of $w^{\prime}$ is rejected by
$\mathcal{A}$. Note that this is equivalent to: For every
$w=\sigma_{1}\dots\sigma_{n}\in\mathcal{L}(\mathcal{A})$ there exist
$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})\in\\{q_{n},q_{n+1}\\}$.

We prove the compositionality of $\mathcal{A}$ by specifying a DFA
$\mathcal{A}_{i,l}$ for each possible pair
$i\in\\{0,\dots,n-2\\},l\in\\{2,\dots,n-i\\}$. These DFAs will reject the
extensions of words $w\in L,|w|=n$. In addition to these DFAs we will use the
DFAs $\mathcal{A}_{0},\hat{\mathcal{A}}_{d},\mathcal{A}_{\underline{i}}$ which
we have discussed in Section A.2.

$q_{0}$$q_{1}$$q_{i-1}$$q_{i}$$q_{i+1}$$q_{i+l-2}$$q_{i+l}$$q_{i+l+1}$$q_{n-1}$$q_{n}$$q_{n+1}$$\Sigma_{0,1}$$\Sigma_{0,i-1}$$\Sigma_{0,i},\Sigma_{0,i+l-1}$$\Sigma_{0,i+1}$$\Sigma_{0,i+l-2}$$\Sigma_{0,i+l}$$\Sigma_{0,i+l+1}$$\Sigma_{0,n-1}$$\Sigma_{0,n}$$\Sigma_{0,n+1}$$\Sigma_{i-1,i}$$\overline{\Sigma^{\prime}}$$\Sigma^{\prime}$$\Sigma$$\Sigma$$\Sigma$$\Sigma$$\Sigma$$\Sigma$
Figure 6: DFA $\mathcal{A}_{i,l}$ for
$i\in\\{0,\dots,n-2\\},l\in\\{2,\dots,n-i\\}$. The transitions exiting $q_{0}$
are given. For $j\in\\{1,\dots,i-1\\}$, the transitions are omitted for
readability purposes. It is
$\Sigma^{\prime}=\bigcup_{j=i+l}^{n+1}\Sigma_{i,j}$.

The construction of DFA $\mathcal{A}_{i,l}$ is specified in Figure 6.
Additionally, we provide a formal definition. Let
$i\in\\{0,\dots,n-2\\},l\in\\{2,\dots,n-i\\}$ and let
$\Sigma^{\prime}=\bigcup_{j=i+l}^{n+1}\Sigma_{i,j}$. We define
$\mathcal{A}_{i,l}=(Q_{i,l},\Sigma,q_{0},\delta_{i,l},F_{i,l})$ where:

$\displaystyle Q_{i,l}$
$\displaystyle=\\{q_{0},\dots,q_{i+l-2},q_{i+l},\dots,q_{n+1}\\}$
$\displaystyle F_{i,l}$ $\displaystyle=Q_{i,l}\setminus\\{q_{n+1}\\}$
$\displaystyle\delta_{i,l}(q_{j},\sigma)$
$\displaystyle=\begin{cases}\delta(q_{j},\sigma)&\text{ if $j<i$ and
$\delta(q_{j},\sigma)\neq q_{i+l-1}$}\\\ q_{i}&\text{ if $j<i$ and
$\delta(q_{j},\sigma)=q_{i+l-1}$}\\\ q_{i+1}&\text{ if $j=i$ and
$\sigma\notin\Sigma^{\prime}$}\\\ q_{i+l}&\text{ if $j=i$ and
$\sigma\in\Sigma^{\prime}$}\\\ q_{j+1}&\text{ if $i<j<n+1$ and $j\neq
i+l-2$}\\\ q_{i}&\text{ if $j=i+l-2$}\\\ q_{n+1}&\text{else, thus if
$j=n+1$}\end{cases}.$

The following lemma states properties of $\mathcal{A}_{i,l}$:

######  Lemma A.18.

Let $i\in\\{0,\dots,n-2\\}$ and $l\in\\{2,\dots,n-i\\}$. Consider the DFA
$\mathcal{A}_{i,l}$. The following assertions hold:

$\mathcal{A}_{i,l}\in\alpha(\mathcal{A})$.

Let $w=\sigma_{1}\dots\sigma_{n}\in\Sigma^{n}$ with
$\delta(q_{0},\sigma_{1}\dots\sigma_{i})=q_{i}$ and
$\sigma_{i+l}\in\Sigma^{\prime}$. The DFA $\mathcal{A}_{i,l}$ then rejects
every extension of $w$. That is, $wv\notin\mathcal{L}(\mathcal{A}_{i,l})$ for
each $v\in\Sigma^{+}$.

######  Proof A.19.

Let $i\in\\{0,\dots,n-2\\},l\in\\{2,\dots,n-i\\}$. Consider the DFA
$\mathcal{A}_{i,l}=(Q_{i,l},\Sigma,q_{0},\delta_{i,l},F_{i,l})$.

First, we turn to (i) and argue that
$\mathcal{A}_{i,l}\in\alpha(\mathcal{A})$. Note that
$|\mathcal{A}_{i,l}|=n+1<n+2=\text{ind}(\mathcal{A})$. Therefore, we only have
to argue that
$\mathcal{L}(\mathcal{A})\subseteq\mathcal{L}(\mathcal{A}_{i,l})$. But this is
easy to see, since for every $w\in\Sigma^{*}$ and
$s,t\in\\{0,\dots,n+1\\},t\neq i+l-1$ such that $\delta(q_{0},w)=q_{s}$ and
$\delta_{i,l}(q_{0},w)=q_{t}$, we have $s\geq t$. Since this implies
$\delta_{i,l}(q_{0},w)=q_{n+1}$ only if $\delta(q_{0},w)=q_{n+1}$ and since
$q_{n+1}$ is the only rejecting state of $\mathcal{A}_{i,l}$, we have
$\mathcal{L}(\mathcal{A})\subseteq\mathcal{L}(\mathcal{A}_{i,l})$. We have
shown that $\mathcal{A}_{i,l}\in\alpha(\mathcal{A})$ and are done with (i).

Second, we turn to (ii). Let $w=\sigma_{1}\dots\sigma_{n}\in\Sigma^{n}$ with
$\delta(q_{0},\sigma_{1}\dots\sigma_{i})=q_{i}$ and
$\sigma_{i+l}\in\Sigma^{\prime}$. Then we have
$\delta_{i,l}(q_{0},\sigma_{1}\dots\sigma_{i+l})=q_{j}$ for a $j\geq i+l$. To
be more precise, we have $j=i+l$ if $\sigma_{i+1}\notin\Sigma^{\prime}$,
otherwise we have $j>i+l$.

Note that when in state $q_{j}$ the DFA $\mathcal{A}_{i,l}$ rejects after
reading $(n+1)-j\leq(n+1)-(i+l)$ additional letters. Therefore, every
extension of $w$ is rejected by $\mathcal{A}_{i,l}$. We are done with (ii).
The proof of Lemma A.18 is complete.

Note that Lemma A.18 (ii) critically hinges on
$\sigma_{i+l}\in\Sigma^{\prime}$. We now introduce a rather technical lemma,
which allows us to use the DFAs $\mathcal{A}_{i,l}$ to reject the extensions
of words $w\in L,|w|=n$.

######  Lemma A.20.

Let $w=\sigma_{1}\dots\sigma_{n}\in\Sigma^{n}$ with
$w\in\mathcal{L}(\mathcal{A})$ such that there exist
$i\in\\{0,\dots,n-2\\},l\in\\{2,\dots,n-i\\}$ with
$\delta(q_{0},\sigma_{1}\dots\sigma_{i}\sigma_{i+l}\dots\sigma_{n})\in\\{q_{n},q_{n+1}\\}$.
Let $i$ be the maximal value for which such an $l$ exists. Then there exists a
$j\in\\{i+l,\dots,n+1\\}$ such that $\sigma_{i+l}\in\Sigma_{i,j}$. That is,
$\sigma_{i+l}\in\Sigma^{\prime}$ holds.

######  Proof A.21.

Before we start, we define $\text{index}(q_{j})=j$ for each $q_{j}\in Q$.

Let $w,i,l$ be as required.

Note that there is a $k\in\\{0,\dots,n-(i+l)\\}$ such that
$\text{index}(\delta(q_{0},\sigma_{1}\dots\sigma_{i}\sigma_{i+l}\dots\sigma_{i+l+k}))\geq
i+l+k$. This is obvious, since for $k=n-(i+l)$ we have:

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

With this observation in hand, we can turn to the actual proof. We employ a
proof by contradiction and therefore assume $\sigma_{i,l}\in\Sigma_{i,j}$ for
a $j\in\\{i+1,\dots,i+l-1\\}$.

We briefly consider the case $i=n-2$. Then
$\delta(q_{0},\sigma_{1}\dots\sigma_{i}\sigma_{i+l})=\delta(q_{0},\sigma_{1}\dots\sigma_{n-2}\sigma_{n})=q_{n-1}$
holds. This is a contradiction to
$\delta(q_{0},\sigma_{1}\dots\sigma_{i}\sigma_{i+l})\in\\{q_{n},q_{n+1}\\}$.
Therefore, we can assume $i<n-2$.

We will show that $\sigma_{i,l}\in\Sigma_{i,j}$ for a
$j\in\\{i+1,\dots,i+l-1\\}$ and $i<n-2$ implies the existence of
$i^{\prime}\in\\{0,\dots,n-2\\},l^{\prime}\in\\{2,\dots,n-i^{\prime}\\}$ such
that
$\delta(q_{0},\sigma_{1}\dots\sigma_{i^{\prime}}\sigma_{i^{\prime}+l^{\prime}}\dots\sigma_{n})\in\\{q_{n},q_{n+1}\\}$
and $i^{\prime}>i$, which contradicts the selection of $i$ as the largest
possible value.

Note that with $\sigma_{i+l}\in\Sigma_{i,j}$ we have
$\text{index}(\delta(q_{0},\sigma_{1}\dots\sigma_{i}\sigma_{i+l}))=\text{index}(\delta(q_{i},\sigma_{i+l}))=\text{index}(q_{j})=j<i+l$.
Additionally, with the above observation there exists a
$k\in\\{0,\dots,n-(i+l)\\},k>0$ such that
$\text{index}(\delta(q_{0},\sigma_{1}\dots\sigma_{i}\sigma_{i+l}\dots\sigma_{i+l+k}))\geq
i+l+k$. Let $k$ be the minimal value for which this holds. Then we have:

$\displaystyle k\geq 1,$
$\displaystyle\text{index}(\delta(q_{0},\sigma_{1}\dots\sigma_{i}\sigma_{i+l}\dots\sigma_{i+l+k-1}))<i+l+k-1,$
$\displaystyle\text{index}(\delta(q_{0},\sigma_{1}\dots\sigma_{i}\sigma_{i+l}\dots\sigma_{i+l+k}))\geq
i+l+k.$

We define
$i^{\prime}=\text{index}(\delta(q_{0},\sigma_{1}\dots\sigma_{i}\sigma_{i+l}\dots\sigma_{i+l+k-1}))$.
Note that $i^{\prime}<i+l+k-1<i+l+k\leq n$ and thus $i^{\prime}\leq n-2$.
Further, we have:

$\displaystyle i^{\prime}$
$\displaystyle=\text{index}(\delta(q_{0},\sigma_{1}\dots\sigma_{i}\sigma_{i+l}\dots\sigma_{i+l+k-1}))$
$\displaystyle\geq\text{index}(\delta(q_{0},\sigma_{1}\dots\sigma_{i}\sigma_{i+l}\dots\sigma_{i+l+1-1}))$
$\displaystyle=\text{index}(\delta(q_{0},\sigma_{1}\dots\sigma_{i}\sigma_{i+l}))$
$\displaystyle=\text{index}(q_{j})$ $\displaystyle=j$ $\displaystyle>i.$

Thus, we have $i^{\prime}\in\\{i+1,\dots,n-2\\}$ and $i<n-2$. Therefore, we
have $i^{\prime}\in\\{0,\dots,n-2\\}$ with $i^{\prime}>i$.

Now note that:

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

Let $l^{\prime}=(i+l+k)-i^{\prime}$. Then
$\delta(q_{0},\sigma_{1}\dots\sigma_{i^{\prime}}\sigma_{i^{\prime}+l^{\prime}}\dots\sigma_{n})\in\\{q_{n},q_{n+1}\\}$
holds. Additionally, as explained above, we have
$i^{\prime}\in\\{0,\dots,n-2\\}$ with $i^{\prime}>i$. Further, because of
$i^{\prime}<i+l+k-1$ we have
$l^{\prime}=(i+l+k)-i^{\prime}>(i+l+k)-(i+l+k-1)=1$. That is, $l^{\prime}\geq
2$. Finally, because of $k\leq n-(i+l)$ we have
$l^{\prime}+i^{\prime}=(i+l+k-i^{\prime})+i^{\prime}=i+l+k\leq
i+l+(n-(i+l))=n$. That is, $l^{\prime}+i^{\prime}\leq n$ and therefore
$l^{\prime}\leq n-i^{\prime}$. Taken together we get
$l^{\prime}\in\\{2,\dots,n-i^{\prime}\\}$.

To summarize, we have
$i^{\prime}\in\\{0,\dots,n-2\\},l^{\prime}\in\\{2,\dots,n-i^{\prime}\\}$ with
$i^{\prime}>i$ such that
$\delta(q_{0},\sigma_{1}\dots\sigma_{i^{\prime}}\sigma_{i^{\prime}+l^{\prime}}\dots\sigma_{n})\in\\{q_{n},q_{n+1}\\}$.
This is a contradiction to the selection of $i$ as the largest possible value.

In conclusion, we have proven by contradiction that there exists a
$j\in\\{i+l,\dots,n+1\\}$ such that $\sigma_{i+l}\in\Sigma_{i,j}$. That is,
$\sigma_{i+l}\in\Sigma^{\prime}$. The proof of Lemma A.20 is complete.

With Lemmas A.18 and A.20 in hand, it is easy to prove 1 (1).

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

We assume that $\mathcal{A}$ has the CEP. We prove the compositionality of
$\mathcal{A}$ by showing:

$\displaystyle L$
$\displaystyle=\mathcal{L}(\mathcal{A}_{0})\cap\mathcal{L}(\hat{\mathcal{A}}_{d})$
$\displaystyle\cap\bigcap_{m=1}^{n-1}\bigcap_{\underline{i}\in
I_{m}}\mathcal{L}(\mathcal{A}_{\underline{i}})\cap\bigcap_{i\in\\{0,\dots,n-2\\},l\in\\{2,\dots,n-i\\}}\mathcal{L}(\mathcal{A}_{i,l}),$

where $d\in\\{0,\dots,n\\}$ can be arbitrarily selected. We denote the
language created by the decomposition on the right hand side with $L_{\cap}$.

The proof is similar to the proof of 1 (1).

Note that with Lemmas 3.2 and A.18 each of the DFAs used for the decomposition
is in $\alpha(\mathcal{A})$, which implies that they are sufficiently small
and that $L\subseteq L_{\cap}$ holds. Therefore, we only need to show
$L_{\cap}\subseteq L$.

Let $w=\sigma_{1}\dots\sigma_{m}\in\Sigma^{m}$ with $w\notin L$. Similar to
the proof of 1 (1) we begin by assuming:

$\displaystyle w$
$\displaystyle\notin\mathcal{L}(\mathcal{A}_{0})\cap\mathcal{L}(\hat{\mathcal{A}}_{d})$
$\displaystyle\cap\bigcap_{m=1}^{n-1}\bigcap_{\underline{i}\in
I_{m}}\mathcal{L}(\mathcal{A}_{\underline{i}}).$

Then we are done immediately.

Thus, we assume that $w$ is not rejected by these DFAs. With Lemma 3.2 (ii)
this implies that $w$ is an extension of a word $u\in L,|u|=n$. That is, $m>n$
and $\sigma_{1}\dots\sigma_{n}\in L$. Then per requirement there exist
$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})\in\\{q_{n},q_{n+1}\\}$.
Let $i$ be the largest value for which such an $l$ exists. With Lemma A.20
this implies $\sigma_{i+l}\in\Sigma_{i,j}$ for a $j\in\\{i+l,\dots,n+1\\}$.
Then with Lemma A.18 we have $w\notin\mathcal{L}(\mathcal{A}_{i,l})$, since
$\delta(q_{0},\sigma_{1}\dots\sigma_{i})=q_{i}$ and
$\sigma_{i+l}\in\bigcup_{j=i+l}^{n+1}\Sigma_{i,j}$. Therefore, we have:

$\displaystyle
w\notin\bigcap_{i\in\\{0,\dots,n-2\\},l\in\\{2,\dots,n-i\\}}\mathcal{L}(\mathcal{A}_{i,l}).$

This implies $w\notin L_{\cap}$. Thus, we have $L_{\cap}\subseteq L$. The
proof of 1 (1) is complete.

We have proven that $\mathcal{A}$ is composite if it has the CEP. It is
noteworthy that we have made no requirements regarding the accepting and
rejecting states of $\mathcal{A}$, since the CEP implies compositionality
regardless of these states. We have introduced a new type of DFA,
$\mathcal{A}_{i,l}$, which rejects the extensions of words $w\in L,|w|=n$.
Therefore, if $\mathcal{A}$ has the CEP then the more complicated construction
for non-safety DFAs detailed in Section A.2 is not necessary.

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

Finally, we consider 1 (1). Our goal is to show that $\mathcal{A}$ is prime if
it is a safety DFA and does not have the CEP.

Therefore, we assume that $\mathcal{A}$ is a safety DFA. That is,
$F=Q\setminus\\{q_{n+1}\\}$. We begin by proving primality of $\mathcal{A}$ if
$\mathcal{A}$ does not have the CEP and if another condition is met as well.
Then we will show that this condition is implied by $\mathcal{A}$ not having
the CEP. Thus, the ADFA $\mathcal{A}$ is prime if it does not have the CEP.

First, we prove:

######  Lemma A.23.

The ADFA $\mathcal{A}$ is prime, if:

  1. 1.

$\neg(\Sigma_{n-1,n}\subseteq\bigcup_{j=0}^{n-1}\Sigma_{j,n+1})$, and

  2. 2.

it does not have the CEP.

######  Proof A.24.

Assume that the two conditions outlined in the lemma hold.

With the first condition there is a $\sigma\in\Sigma_{n-1,n}$ such that
$\sigma\notin\bigcup_{j=0}^{n-1}\Sigma_{j,n+1}$. With the second condition
there is a word $w=\sigma_{1}\dots\sigma_{n}\in\Sigma^{n}$ with
$w\in\mathcal{L}(\mathcal{A})$ such that
$\delta(q_{0},\sigma_{1}\dots\sigma_{i}\sigma_{i+l}\dots\sigma_{n})\notin\\{q_{n},q_{n+1}\\}$
holds for every $i\in\\{0,\dots,n-2\\},l\in\\{2,\dots,n-i\\}$. We will show
that $w\sigma$ is a primality witness of $\mathcal{A}$.

Let $\mathcal{B}=(S,\Sigma,s_{0},\eta,G)\in\alpha(\mathcal{A})$. It is easy to
see that, since $\mathcal{A}$ is a safety DFA, we can assume w.l.o.g. that
$\mathcal{B}$ is a safety DFA as well. See [16] for more details. We will show
$w\sigma\in\mathcal{L}(\mathcal{B})$.

If $\mathcal{L}(\mathcal{B})=\Sigma^{*}$ then
$w\sigma\in\mathcal{L}(\mathcal{B})$ trivially holds. Therefore, we assume
$\mathcal{L}(\mathcal{B})\subset\Sigma^{*}$. Since $\mathcal{B}$ is a minimal
safety DFA and has therefore only one rejecting state, which is a rejecting
sink, the DFA $\mathcal{B}$ does not enter this sink in the run on $w$. This
implies that in the run on $w$ the DFA $\mathcal{B}$ can pass only through
$|\mathcal{B}|-1\leq(n+1)-1=n$ different states. Therefore, there are
$i,j\in\\{0,\dots,n\\}$ with $i<j$ such that
$\eta(s_{0},\sigma_{1}\dots\sigma_{i})=\eta(s_{0},\sigma_{1}\dots\sigma_{j})$.

Case 1: $j=n$.

Then we have:

$\displaystyle\eta(s_{0},w\sigma)$ $\displaystyle=$
$\displaystyle\eta(\eta(s_{0},w),\sigma)$ $\displaystyle=$
$\displaystyle\eta(\eta(s_{0},\sigma_{1}\dots\sigma_{n}),\sigma)$
$\displaystyle=$
$\displaystyle\eta(\eta(s_{0},\sigma_{1}\dots\sigma_{i}),\sigma)$
$\displaystyle=$ $\displaystyle\eta(s_{0},\sigma_{1}\dots\sigma_{i}\sigma).$

Since $w\in\mathcal{L}(\mathcal{A})$, we further have
$\delta(q_{0},\sigma_{1}\dots\sigma_{i})=q_{i}$ for $i<j=n$. Additionally, we
have per requirement $\sigma\notin\bigcup_{j=0}^{n-1}\Sigma_{j,n+1}$ and
therefore in particular $\sigma\notin\Sigma_{i,n+1}$. Thus, we have
$\delta(q_{0},\sigma_{1}\dots\sigma_{i}\sigma)=\delta(q_{i},\sigma)\neq
q_{n+1}$ and therefore
$\sigma_{1}\dots\sigma_{i}\sigma\in\mathcal{L}(\mathcal{A})$. Since
$\eta(s_{0},w\sigma)=\eta(s_{0},\sigma_{1}\dots\sigma_{i}\sigma)$, this
implies $w\sigma\in\mathcal{L}(\mathcal{B})$. We are done with Case 1.

Case 2: $j<n$.

Then we have:

$\displaystyle\eta(s_{0},w\sigma)$ $\displaystyle=$
$\displaystyle\eta(\eta(s_{0},w),\sigma)$ $\displaystyle=$
$\displaystyle\eta(\eta(s_{0},\sigma_{1}\dots\sigma_{j}),\sigma_{j+1}\dots\sigma_{n}\sigma)$
$\displaystyle=$
$\displaystyle\eta(\eta(s_{0},\sigma_{1}\dots\sigma_{i}),\sigma_{j+1}\dots\sigma_{n}\sigma)$
$\displaystyle=$
$\displaystyle\eta(s_{0},\sigma_{1}\dots\sigma_{i}\sigma_{j+1}\dots\sigma_{n}\sigma).$

Additionally, we have $0\leq i<j<n$ and therefore $i\leq n-2$. Further, with
$i<j<n$ we have $i+1<j+1<n+1$ and therefore $i+2\leq j+1\leq n$ which implies
$2\leq(j+1)-i\leq n-i$. Select $l=(j+1)-i$. Now we have
$i\in\\{0,\dots,n-2\\},l\in\\{2,\dots,n-i\\}$ with
$\eta(s_{0},w)=\eta(s_{0},\sigma_{1}\dots\sigma_{i}\sigma_{i+l}\dots\sigma_{n})$.

With the second condition
$\delta(q_{0},\sigma_{1}\dots\sigma_{i}\sigma_{i+l}\dots\sigma_{n})=q_{k}$
holds for a $k\in\\{0,\dots,n-1\\}$. With condition one we then have
$\sigma\notin\Sigma_{k,n+1}$ and therefore
$\delta(q_{0},\sigma_{1}\dots\sigma_{i}\sigma_{i+l}\dots\sigma_{n}\sigma)=\delta(q_{k},\sigma)\neq
q_{n+1}$. Thus, we have
$\sigma_{1}\dots\sigma_{i}\sigma_{i+l}\dots\sigma_{n}\sigma\in\mathcal{L}(\mathcal{A})$.
Since
$\eta(s_{0},w\sigma)=\eta(s_{0},\sigma_{1}\dots\sigma_{i}\sigma_{i+l}\dots\sigma)$
holds, this implies $w\sigma\in\mathcal{L}(\mathcal{B})$. We are done with
Case 2.

With Cases 1 and 2 we have shown $w\sigma\in\mathcal{L}(\mathcal{B})$.
Therefore, every DFA in $\alpha(\mathcal{A})$ accepts $w\sigma$. This means
that $w\sigma$ is a primality witness of $\mathcal{A}$, which implies the
primality of $\mathcal{A}$. The proof of Lemma A.23 is complete.

We have established a sufficient condition for the primality of $\mathcal{A}$.
Now we proof that the second condition, the ADFA $\mathcal{A}$ not having the
CEP, implies the first condition. More precisely, we prove that already a