# On Sensitivity of
Compact Directed Acyclic Word Graphs

Hiroto Fujimaru  Department of Physics, Kyushu University, Fukuoka, Japan
<EMAIL_ADDRESS>Yuto Nakashima  Department of
Informatics, Kyushu University, Japan {nakashima.yuto.003,
<EMAIL_ADDRESS>Shunsuke Inenaga  Department of
Informatics, Kyushu University, Japan {nakashima.yuto.003,
<EMAIL_ADDRESS>
###### Abstract

_Compact directed acyclic word graphs_ (_CDAWGs_) [Blumer et al. 1987] are a
fundamental data structure on strings with applications in text pattern
searching, data compression, and pattern discovery. Intuitively, the CDAWG of
a string $T$ is obtained by merging isomorphic subtrees of the suffix tree
[Weiner 1973] of the same string $T$, thus CDAWGs are a compact indexing
structure. In this paper, we investigate the sensitivity of CDAWGs when a
single character edit operation (insertion, deletion, or substitution) is
performed at the left-end of the input string $T$, namely, we are interested
in the worst-case increase in the size of the CDAWG after a left-end edit
operation. We prove that if $\mathsf{e}$ is the number of edges of the CDAWG
for string $T$, then the number of new edges added to the CDAWG after a left-
end edit operation on $T$ is less than $\mathsf{e}$. Further, we present
almost matching lower bounds on the sensitivity of CDAWGs for all cases of
insertion, deletion, and substitution.

##  1 Introduction

_Compact directed acyclic word graphs_ (_CDAWGs_) [4] are a fundamental data
structure on strings that have applications in fields including text pattern
searching [6, 8], data compression [2, 13], and pattern discovery [14].
Intuitively, the CDAWG of a string $T$, denoted $\mathsf{CDAWG}(T)$, is
obtained by merging isomorphic subtrees of the suffix tree [15] of the same
string $T$. Thus the size of the CDAWG is always smaller than that of the
suffix tree.

It is well known that the nodes of $\mathsf{CDAWG}(T)$ correspond to _maximal
repeats_ in $T$, and the number $\mathsf{e}$ of right-extensions of maximal
repeats in $T$, which is equal to the number of edges of $\mathsf{CDAWG}(T)$,
has been used as one of repetitiveness measures of strings. Namely, when
$\mathsf{e}$ is small, then the string contains a lot of repetitive substrings
hence being well compressible. Indeed, it is known that $\mathsf{e}$ can be as
small as $\Theta(\log n)$ with highly repetitive strings [11]. Further, one
can obtain a _grammar-based compression_ of size $O(\mathsf{e})$ via the CDAWG
of the input string $T$ [2]. Some relations between $\mathsf{e}$ and the
number $\mathsf{r}$ of equal-letter runs in the _Burrows-Wheeler transform_
(_BWT_) [5] have also been investigated [3].

Recently, Akagi et al. [1] proposed the notion of _sensitivity_ of string
repetitiveness measures and string compressors, including the aforementioned
$\mathsf{e}$ and $\mathsf{r}$, the smallest _string attractor_ size $\gamma$
[9], the _substring complexity_ $\delta$ [10], and the Lempel-Ziv parse size
$\mathsf{z}$ [16]. The sensitivity of a repetitiveness measure $\mathsf{c}$
asks how much the measure size increases when a single-character edit
operation is performed on the input string, and thus the sensitivity allows
one to evaluate the robustness of the measure/compressor against errors/edits.

This paper investigates the sensitivity of CDAWGs when a single character edit
operation (insertion, deletion, or substitution) is performed at the left-end
of the input string $T$, namely, we are interested in the worst-case increase
in the size of the CDAWG after an left-end edit operation. We prove that if
$\mathsf{e}$ is the number of edges of the CDAWG for string $T$, then the
number of new edges which are added to the CDAWG after an left-edit operation
on $T$ is always less than $\mathsf{e}$. Further, we present almost matching
lower bounds on the sensitivity of CDAWGs for any left-end insertion,
deletion, and substitution (see Table 1 for a summary of these results). We
generalize our lower-bound instances for left-end insertion to _leftward
online construction_ of the CDAWG, and show that it requires $\Omega(n^{2})$
time. This contrasts with the case of _rightward online CDAWG construction_
for which a linear-time algorithm exists [8].

Table 1: Our results: additive sensitivity of CDAWGs with left-end edit operations. edit operation | upper bound | lower bound
---|---|---
left-end insertion ($T\Rightarrow aT$) | $\mathsf{e}-1$ | $\mathsf{e}-2$
left-end deletion ($T\Rightarrow T[2..|T|]$) | $\mathsf{e}-2$ | $\mathsf{e}-4$
left-end substitution ($T=aS\Rightarrow bS=T^{\prime}$) | $\mathsf{e}$ | $\mathsf{e}-3$

A full version of this paper can be found in [7].

####  1.0.1 Related work.

Akagi et al. [1] presented lower bounds when a new character is deleted (resp.
substituted) in the middle of the string, with a series of strings for which
the size $\mathsf{e}$ of the CDAWG additively increases by $\mathsf{e}-4$
(resp. $\mathsf{e}-2$). They also showed a lower bound when a new character is
inserted at the _right-end_ of the string, showing a series of strings for
which the size of the CDAWG additively increases by $\mathsf{e}-2$. While an
additive $\mathsf{e}+O(1)$ upper bound for the case of right-end insertion
readily follows from the _rightward_ online construction of CDAWGs [8], no
non-trivial upper bounds for the other edit operations, including our case of
left-end edit operations, are known. Our $\Omega(n^{2})$ lower-bound for
leftward online construction of the CDAWG extends the quadratic lower-bound
for maintaining the CDAWG in the sliding window model [12] (remark that fixing
the right-end of the sliding window is equivalent to our leftward online
construction).

##  2 Preliminaries

Let $\Sigma$ be an _alphabet_ of size $\sigma$. An element of $\Sigma^{*}$ is
called a _string_. For a string $T\in\Sigma^{*}$, the length of $T$ is denoted
by $|T|$. The _empty string_ , denoted by $\varepsilon$, is the string of
length $0$. Let $\Sigma^{+}=\Sigma^{*}\setminus\\{\varepsilon\\}$. If $T=uvw$,
then $u$, $v$, and $w$ are called a _prefix_ , _substring_ , and _suffix_ of
$T$, respectively. The sets of prefixes, substrings, and suffixes of string
$T$ are denoted by $\mathsf{Prefix}(T)$, $\mathsf{Substr}(T)$, and
$\mathsf{Suffix}(T)$, respectively. For a string $T$ of length $n$, $T[i]$
denotes the $i$th character of $T$ for $1\leq i\leq n$, and
$T[i..j]=T[i]\cdots T[j]$ denotes the substring of $T$ that begins at position
$i$ and ends at position $j$ on $T$ for $1\leq i\leq j\leq n$. For two strings
$u$ and $T$, let $\mathsf{BegPos}(u,T)=\\{i\mid T[i..i+|u|-1]=u\\}$ and
$\mathsf{EndPos}(u,T)=\\{i\mid T[i-|u|+1..i]=u\\}$ denote the sets of
beginning positions and the set of ending positions of $u$ in $T$,
respectively.

For any substrings $u,v\in\mathsf{Substr}(T)$ of a string $T$, we write
$u\equiv^{\mathrm{L}}_{T}v$ iff $\mathsf{EndPos}(u,T)=\mathsf{EndPos}(v,T)$.
Let $[{\cdot}]^{\mathrm{L}}_{T}$ denote the equivalence class of strings under
$\equiv^{\mathrm{L}}_{T}$. For $x\in\mathsf{Substr}(T)$, let
$\mathsf{long}([{x}]^{\mathrm{L}}_{T})$ denote the longest member of
$[{x}]^{\mathrm{L}}_{T}$. Let
$\mathsf{LeftM}(T)=\\{\mathsf{long}([{x}]^{\mathrm{L}}_{T})\mid
x\in\mathsf{Substr}(T)\\}$. Any element $u\in\mathsf{LeftM}(T)$ is said to be
_left-maximal_ in $T$, since there are two distinct characters $c,d\in\Sigma$
such that $cu,du\in\mathsf{Substr}(T)$, or $u\in\mathsf{Prefix}(T)$. For any
non-longest element
$y\in[{x}]^{\mathrm{L}}_{T}\setminus\\{\mathsf{long}([{x}]^{\mathrm{L}}_{T})\\}$
there exists a unique non-empty string $\alpha$ such that $\alpha
y=\mathsf{long}([{x}]^{\mathrm{L}}_{T})$, i.e. any occurrence of $y$ in $T$ is
immediately preceded by $\alpha$.

Similarly, we write $u\equiv^{\mathrm{R}}_{T}v$ iff
$\mathsf{BegPos}(u,T)=\mathsf{BegPos}(v,T)$. Let $[{\cdot}]^{\mathrm{R}}_{T}$
denote the equivalence class of strings under $\equiv^{\mathrm{R}}_{T}$. For
$x\in\mathsf{Substr}(T)$, let $\mathsf{long}([{x}]^{\mathrm{R}}_{T})$ denote
the longest member of $[{x}]^{\mathrm{R}}_{T}$. Let
$\mathsf{RightM}(T)=\\{\mathsf{long}([{x}]^{\mathrm{R}}_{T})\mid
x\in\mathsf{Substr}(T)\\}$. Any element $u\in\mathsf{RightM}(T)$ is said to be
_right-maximal_ in $T$, since there are two distinct characters $c,d\in\Sigma$
such that $uc,ud\in\mathsf{Substr}(T)$, or $u\in\mathsf{Suffix}(T)$. For any
non-longest element
$y\in[{x}]^{\mathrm{R}}_{T}\setminus\\{\mathsf{long}([{x}]^{\mathrm{R}}_{T})\\}$
there exists a unique non-empty string $\beta$ such that
$y\beta=\mathsf{long}([{x}]^{\mathrm{R}}_{T})$, i.e. any occurrence of $y$ in
$T$ is immediately followed by $\beta$. Let
$\mathsf{M}(T)=\mathsf{LeftM}(T)\cap\mathsf{RightM}(T)$. Any element of
$\mathsf{M}(T)$ is said to be _maximal_ in $T$.

The _compact directed acyclic word graph_ (_CDAWG_) of a string $T$, denoted
$\mathsf{CDAWG}(T)=(\mathsf{V},\mathsf{E})$, is an edge-labeled DAG such that

$\displaystyle\mathsf{V}_{T}$ $\displaystyle=$
$\displaystyle\\{[{x}]^{\mathrm{L}}_{T}\mid x\in\mathsf{RightM}(T)\\},$
$\displaystyle\mathsf{E}_{T}$ $\displaystyle=$
$\displaystyle\\{([{x}]^{\mathrm{L}}_{T},\beta,[{x\beta}]^{\mathrm{L}}_{T})\mid\beta\in\Sigma^{+},x,x\beta\in\mathsf{RightM}(T),y\beta\in[{x\beta}]^{\mathrm{L}}_{T}\mbox{
for any }y\in[{x}]^{\mathrm{L}}_{T}\\}.$

Figure 1: Illustration for $\mathsf{CDAWG}(T)$ of string
$T=(ab)^{4}c(ab)^{3}$. Every substring of $T$ can be spelled out from a
distinct path from the source $\varepsilon$. There is a one-to-one
correspondence between the maximal substrings in
$\mathsf{M}(T)=\\{\varepsilon,ab,(ab)^{2},(ab)^{3},(ab)^{4}c(ab)^{3}\\}$ and
the nodes of $\mathsf{CDAWG}(T)$. The number of right-extensions of
$\mathsf{CDAWG}(T)$ is the number $\mathsf{e}(T)$ of edges, which is 9 in this
example.

See Fig. 1 for a concrete example of CDAWGs. Intuitively, the strings in
$\mathsf{RightM}(T)$ correspond to the nodes of the suffix tree [15] of $T$,
and the operator $[{\cdot}]^{\mathrm{L}}_{T}$ merges the isomorphic subtrees
of the suffix tree. Recall that the nodes of the suffix tree for $T$
correspond to the right-maximal substrings of $T$. Since
$\mathsf{long}([{x}]^{\mathrm{L}}_{T})$ is a maximal substring of $T$ for any
$x\in\mathsf{RightM}(T)$, we have the following fact:

######  Fact 1.

There is a one-to-one correspondence between the elements of $\mathsf{M}(T)$
and the nodes of $\mathsf{CDAWG}(T)$.

We can regard each element of $\mathsf{M}(T)$ as a node of $\mathsf{CDAWG}(T)$
by Fact 1. We thus sometimes identify $\mathsf{V}_{T}$ with $\mathsf{M}(T)$
for convenience. For any $x\in\mathsf{M}(T)$, $\mathsf{d}_{T}(x)$ denotes the
out-degree of the node $x$ in $\mathsf{CDAWG}(T)$.

A non-empty substring $x$ of string $T$ is called a _maximal repeat_ in $T$ if
$x$ is maximal in $T$ and $|\mathsf{BegPos}(x,T)|=|\mathsf{EndPos}(x,T)|\geq
2$. We remark that the set of maximal repeats in $T$ coincides with
$\mathsf{M}(T)\setminus\\{\varepsilon,T\\}$, namely the longest elements of
all internal nodes of $\mathsf{CDAWG}(T)$ are maximal repeats in $T$, and they
are the only maximal repeats in $T$.

The _size_ of $\mathsf{CDAWG}(T)=(\mathsf{V}_{T},\mathsf{E}_{T})$ for a string
$T$ of length $n$ is the number $\mathsf{e}(T)=|\mathsf{E}_{T}|$ of edges in
$\mathsf{CDAWG}(T)$, which is also referred to as the number of right-
extensions of maximal repeats in $T$. Using this measure $\mathsf{e}$, we
define the worst-case additive _sensitivity_ of the CDAWG with left-end edit
operations (resp. insertion, deletion, and substitution) by:

$\displaystyle\mathsf{AS}_{\mathrm{LeftIns}}(\mathsf{\mathsf{e}},n)$
$\displaystyle=$
$\displaystyle\max_{T\in\Sigma^{n},a\in\Sigma}\\{\mathsf{e}(aT)-\mathsf{e}(T)\\},$
$\displaystyle\mathsf{AS}_{\mathrm{LeftDel}}(\mathsf{e},n)$ $\displaystyle=$
$\displaystyle\max_{T\in\Sigma^{n}}\\{\mathsf{e}(T[2..n])-\mathsf{e}(T)\\},$
$\displaystyle\mathsf{AS}_{\mathrm{LeftSub}}(\mathsf{e},n)$ $\displaystyle=$
$\displaystyle\max_{T\in\Sigma^{n},a\in\Sigma\setminus\\{T[1]\\}}\\{\mathsf{e}(aT[2..n])-\mathsf{e}(T)\\}.$

For the sensitivity of CDAWGs, we first briefly describe the special case
where both the original string $T$ and an edited string $T^{\prime}$ are
unary. Let $T=a^{n}$. Clearly, every $a^{i}$ with $1\leq i<n$ is a maximal
substring of $T$ and it is only followed by $a$. Thus $\mathsf{e}(T)=n-1$. In
case of insertion, i.e. $T^{\prime}=aT=a^{n+1}$, we similarly have
$\mathsf{e}(T^{\prime})=n$. Thus $\mathsf{e}(T^{\prime})-\mathsf{e}(T)=1$ for
unary strings. Symmetrically, we have
$\mathsf{e}(T^{\prime})-\mathsf{e}(T)=-1$ in the case of deletion with
$T^{\prime}=a^{n-1}$. There is no substitution when $\sigma=1$. In what
follows, we focus on the case where $\sigma\geq 2$.

##  3 Sensitivity of CDAWGs with left-end insertions

We consider the worst-case additive sensitivity
$\mathsf{AS}_{\mathrm{LeftIns}}(\mathsf{e},n)$ of $\mathsf{CDAWG}(T)$ when a
new character $a$ is prepended to input string $T$ of length $n$, i.e.
$T^{\prime}=aT$.

###  3.1 Upper bound for $\mathsf{AS}_{\mathrm{LeftIns}}(\mathsf{e},n)$ on
CDAWGs

We divide the value $\mathsf{e}(T^{\prime})-\mathsf{e}(T)$ into two components
$\mathsf{f}_{\mathrm{Ins}}(T)$ and $\mathsf{g}_{\mathrm{Ins}}(T)$ s.t.

  * •

$\mathsf{f}_{\mathrm{Ins}}(T)$ is the total out-degrees of new nodes that
appear in $\mathsf{CDAWG}(aT)$;

  * •

$\mathsf{g}_{\mathrm{Ins}}(T)$ is the total number of new out-going edges of
nodes that already exist in $\mathsf{CDAWG}(T)$.

Clearly
$\mathsf{e}(T^{\prime})-\mathsf{e}(T)\leq\mathsf{f}_{\mathrm{Ins}}(T)+\mathsf{g}_{\mathrm{Ins}}(T)$.
We first consider the above two components separately, and then we merge them
to obtain the desired upper bound.

####  3.1.1 $\mathsf{f}_{\mathrm{Ins}}(T)$: total out-degrees of new nodes.

Suppose $u$ is a new node for $\mathsf{CDAWG}(aT)$, where
$u\notin\mathsf{M}(T)$ and $u\in\mathsf{M}(aT)$. This implies that there is a
new occurrence of $u$ in $aT$ as a prefix. Let $u=ax$. The following is our
key lemma:

######  Lemma 1.

If $ax\notin\mathsf{M}(T)$ and $ax\in\mathsf{M}(aT)$ (i.e. $ax$ is a new node
in $\mathsf{CDAWG}(aT)$), then $x\in\mathsf{M}(T)$. Also,
$\mathsf{d}_{aT}(ax)\leq\mathsf{d}_{T}(x)$.

  * Proof. Since $ax\in\mathsf{Prefix}(aT)$, $x\in\mathsf{Prefix}(T)$. Thus $x$ is left-maximal in $T$. Assume on the contrary that $x$ is not right-maximal in $T$. Then there exists a non-empty string $\beta\in\Sigma^{+}$ such that $x\beta=\mathsf{long}([{x}]^{\mathrm{R}}_{T})$, which means that any occurrence of $x$ in $T$ is immediately followed by $\beta$. Thus $ax$ is also immediately followed by $\beta$ in $aT$, however, this contradicts the precondition that $ax\in\mathsf{M}(aT)$. Thus $x$ is right-maximal in $T$. It immediately follows from $\mathsf{EndPos}(ax,aT)\subseteq\mathsf{EndPos}(x,T)$ that $\mathsf{d}_{aT}(ax)\leq\mathsf{d}_{T}(x)$. ∎

It follows from Lemma 1 that the out-degree of each new node in
$\mathsf{CDAWG}(aT)$ does not exceed the maximum out-degree of
$\mathsf{CDAWG}(T)$. Also, there is an injective mapping from a new node $ax$
in $\mathsf{CDAWG}(aT)$ to an existing node $x$ in $\mathsf{CDAWG}(T)$ by
Lemma 1. Thus $\mathsf{f}_{\mathrm{Ins}}(T)\leq\mathsf{e}(T)$ for any string
$T$.

In the sequel, we give a tighter bound
$\mathsf{f}_{\mathrm{Ins}}(T)\leq\mathsf{e}(T)-1$. For this purpose, we pick
up the case where $x=\varepsilon$, assume that $ax=a$ becomes a new node in
$\mathsf{CDAWG}(aT)$, and compare the out-degree of the source $\varepsilon$
of $\mathsf{CDAWG}(T)$ and the out-degree of the new node $a$ in
$\mathsf{CDAWG}(aT)$. We consider the cases with $\sigma=2$ and with
$\sigma\geq 3$ separately:

######  Lemma 2.

Let $\sigma=2$. If

  1. 1.

$a\notin\mathsf{M}(T)$,

  2. 2.

$a\in\mathsf{M}(aT)$, and

  3. 3.

there exists a string $x\in\mathsf{M}(T)\setminus\\{\varepsilon,T\\}$ such
that $ax\notin\mathsf{M}(T)$ and $ax\in\mathsf{M}(aT)$,

then $\mathsf{d}_{aT}(a)<\mathsf{d}_{T}(\varepsilon)$.

  * Proof. Let $\Sigma=\\{a,b\\}$. We can exclude the case where $T=b^{n}$ due to the following reason: Since $ab^{i}$ for each $1\leq i<n$ is not maximal in $aT=ab^{n}$, no new nodes are created in $\mathsf{CDAWG}(ab^{n})$ (only a new edge labeled $ab^{n}$ from the source to the sink is created).

From now on, consider the case where $T$ contains both $a$ and $b$. This means
that $\mathsf{d}_{T}(\varepsilon)=\sigma=2$. Since $a\in\mathsf{M}(aT)$, $a$
is a node of $\mathsf{CDAWG}(aT)$. Assume on the contrary that
$\mathsf{d}_{aT}(a)=\mathsf{d}_{T}(\varepsilon)$. We then have
$\mathsf{d}_{aT}(a)=2$, which means $aa,ab\in\mathsf{Substr}(aT)$. There are
two cases depending on the first character of $T$:

    * –

If $T[1]=a$, then let $T=aw$. Then, since $aT=aaw$, we have
$ab\in\mathsf{Substr}(T)$. Since $a\notin\mathsf{M}(T)$ (the first
precondition), $b$ is the only character that immediately follows $a$ in $T$,
meaning that $aa\notin\mathsf{Substr}(T)$. Recall that the new node $ax$ must
be a prefix of $aT=aaw$. Since $x\neq\varepsilon$ (the third precondition),
$|ax|\geq 2$, and thus $aa$ is a prefix of $ax$. However, since
$aa\notin\mathsf{Substr}(T)$, $aa$ occurs in $aT$ exactly once as a prefix and
thus $ax$ occurs exactly once in $aT$. This contradicts the third precondition
that $ax$ is a new node in $\mathsf{CDAWG}(aT)$.

    * –

If $T[1]=b$, then we have that $ab\notin\mathsf{Substr}(T)$ by similar
arguments as above. Thus $T$ must be of form $b^{m}a^{n-m}$ with $1\leq m<n$.
Moreover, since $a\notin\mathsf{M}(T)$ and $a\in\mathsf{M}(aT)$ (the first and
second preconditions), we have $T=b^{n-1}a$. Then, for the edited string
$aT=ab^{n-1}a$, any new internal node $ax$ in $\mathsf{CDAWG}(aT)$ must be in
form $ab^{i}$ with $1\leq i<n$. However, each $ax=ab^{i}$ occurs in $aT$
exactly once, meaning that $\mathsf{long}([{ab^{i}}]^{\mathrm{R}}_{aT})=aT$.
This contradicts the third precondition that $ax$ is a new node in
$\mathsf{CDAWG}(aT)$.

Consequently, $\mathsf{d}_{aT}(a)<\mathsf{d}_{T}(\varepsilon)$. ∎

######  Lemma 3.

Let $\sigma\geq 3$. If $a\notin\mathsf{M}(T)$ and $a\in\mathsf{M}(aT)$, then
$\mathsf{d}_{aT}(a)<\mathsf{d}_{T}(\varepsilon)$.

  * Proof. By similar arguments to the proof for Lemma 2, we have that $T$ contains at least three distinct characters, one of which is $a$. Thus $\mathsf{d}_{T}(\varepsilon)=\sigma\geq 3$.

Assume on the contrary that
$\mathsf{d}_{aT}(a)=\mathsf{d}_{T}(\varepsilon)=\sigma\geq 3$. Since
$a\notin\mathsf{M}(T)$ (i.e. $a$ is not maximal in $T$), we have the two
following cases:

    * –

If $a$ is not left-maximal in $T$, then $T[1]\neq a$ and there is a unique
character $b$ ($\neq a$) that immediately precedes $a$ in $T$, meaning that
$aa\notin\mathsf{Substr}(T)$. Since $T[1]\neq a$, we also have
$aa\notin\mathsf{Substr}(aT)$. Thus
$\mathsf{d}_{aT}(a)<\sigma=\mathsf{d}_{T}(\varepsilon)$, a contradiction.

    * –

If $a$ is not right-maximal in $T$, then there is a unique character $b$ that
immediately follows $a$ in $T$. The occurrence of $a$ as a prefix of $aT$ is
followed by $T[1]$, and thus the number $\mathsf{d}_{aT}(a)$ of distinct
characters following $a$ in $aT$ is at most
$2<\sigma=\mathsf{d}_{T}(\varepsilon)$, a contradiction.

Consequently, $\mathsf{d}_{aT}(a)<\mathsf{d}_{T}(\varepsilon)$. ∎

By Lemmas 2 and 3, even if there appear new nodes $ax$ in $\mathsf{CDAWG}(aT)$
corresponding to all existing nodes $x$ in $\mathsf{CDAWG}(T)$, we have a
credit $\mathsf{d}_{T}(\varepsilon)-\mathsf{d}_{aT}(a)\geq 1$ in most cases.
The only exception is when $\sigma=2$ and $\mathsf{M}(T)=\\{\varepsilon,T\\}$.
However, in this specific case $\mathsf{CDAWG}(T)$ consists only of the two
nodes (source and sink), namely $\mathsf{e}(T)=2$. Conversely, we have that
the above arguments hold for any $\mathsf{e}(T)\geq 3$, which leads to the
following:

######  Lemma 4.

For any string $T$ with $\mathsf{e}(T)\geq 3$,
$\mathsf{f}_{\mathrm{Ins}}(T)\leq\mathsf{e}(T)-1$.

####  3.1.2 $\mathsf{g}_{\mathrm{Ins}}(T)$: number of new branches from
existing nodes.

The following lemma states that the out-degrees of most existing nodes of
$\mathsf{CDAWG}(T)$ do not change in $\mathsf{CDAWG}(aT)$, except for a single
unique node that can obtain a single new out-going edge in
$\mathsf{CDAWG}(aT)$:

######  Lemma 5.

For any $y\in\mathsf{Substr}(T)$ such that $y\in\mathsf{M}(T)$ and
$y\in\mathsf{M}(aT)$,
$\mathsf{d}_{aT}(y)\in\\{\mathsf{d}_{T}(y),\mathsf{d}_{T}(y)+1\\}$. Also,
there exists at most one substring $y$ with
$\mathsf{d}_{aT}(y)=\mathsf{d}_{T}(y)+1$. Consequently
$\mathsf{g}_{\mathrm{Ins}}(T)\leq 1$.

  * Proof. Since $y\in\mathsf{M}(T)$ and $y\in\mathsf{M}(aT)$, $y$ is a node in both $\mathsf{CDAWG}(T)$ and $\mathsf{CDAWG}(aT)$. Then we have that:

$\mathsf{d}_{aT}(y)=\begin{cases}\mathsf{d}_{T}(y)+1&\mbox{if
}y\in\mathsf{Prefix}(aT)\mbox{ and $yb$ occurs in $aT$ only as a prefix},\\\
\mathsf{d}_{T}(y)&\mbox{otherwise},\end{cases}$

where $b$ is the character that immediately follows the occurrence of $y$ as a
prefix of $aT$, namely $b=T[|y|]$.

Assume on the contrary that there exist two distinct substrings
$x,y\in\mathsf{M}(T)\cap\mathsf{M}(aT)$ such that
$\mathsf{d}_{aT}(x)=\mathsf{d}_{T}(x)+1$ and
$\mathsf{d}_{aT}(y)=\mathsf{d}_{T}(y)+1$. Since both $x$ and $y$ must be
distinct prefixes of $aT$, we can assume w.l.o.g. that $|x|<|y|$, which means
that $x$ is a proper prefix of $y$. Thus the occurrence of $x$ as a prefix of
$aT$ is immediately followed by the character $c=y[|x|+1]$. We recall that $y$
occurs in $T$ since $y\in\mathsf{M}(T)$. Therefore there is an occurrence of
$x$ in $T$ that is immediately followed by $c$, which leads to
$\mathsf{d}_{aT}(x)=\mathsf{d}_{T}(x)$, a contradiction. ∎

####  3.1.3 Putting all together.

Due to Lemma 4 and Lemma 5, we have an upper bound
$\mathsf{e}(T^{\prime})-\mathsf{e}(T)\leq\mathsf{f}_{\mathrm{Ins}}(T)+\mathsf{g}_{\mathrm{Ins}}(T)\leq\mathsf{e}(T)-1+1=\mathsf{e}(T)$
for $\sigma\geq 2$. We remark that the equality holds only if both of the
following conditions are satisfied:

  1. (a)

For any $x\in\mathsf{M}(T)\setminus\\{\varepsilon\\}$,
$ax\notin\mathsf{M}(T)$, $ax\in\mathsf{M}(aT)$, and
$\mathsf{d}_{aT}(ax)=\mathsf{d}_{T}(x)$;

  2. (b)

There exists a unique string $x\in\mathsf{Substr}(T)$ such that
$\mathsf{d}_{aT}(x)=\mathsf{d}_{T}(x)+1$.

However, in the next lemma, we show that no strings $x$ can satisfy both
Conditions (a) and (b) simultaneously:

######  Lemma 6.

If $ax\notin\mathsf{M}(T)$ and $ax\in\mathsf{M}(aT)$, then
$\mathsf{d}_{aT}(x)=\mathsf{d}_{T}(x)$.

  * Proof. Assume on the contrary that $\mathsf{d}_{aT}(x)\neq\mathsf{d}_{T}(x)$. By Lemma 5 we have that $\mathsf{d}_{aT}(x)=\mathsf{d}_{T}(x)+1$. Then, it also follows from the proof of Lemma 5 that $x$ is a prefix of $aT$ and the character $b=T[|x|]$ that immediately follows the prefix occurrence of $x$ in $aT$ differs from any other characters that immediately follow the occurrences of $x$ in $T$. Namely, we have $b\notin\Sigma^{\prime}=\\{T[i+1]\mid i\in\mathsf{EndPos}(x,T)\\}$. Moreover, by Lemma 1, $ax$ is also a prefix of $aT$. This means that $x$ is a prefix of $ax$, and hence $ax=xb$, which means that $x=a^{|x|}$ and $a=b$. Because $\sigma\geq 2$, $T\neq x$. Since $ax\in\mathsf{M}(aT)$ and $x\neq T$, $ax$ ($=xb$) occurs in $T$. This means that $b=c$ for some $c\in\Sigma^{\prime}$, a contradiction. Thus, $\mathsf{d}_{aT}(x)=\mathsf{d}_{T}(x)$. ∎

We have $\mathsf{e}(T)\geq 3$ only if $|T|\geq 3$. By wrapping up Lemma 4,
Lemma 5, and Lemma 6, we obtain the main result of this subsection:

######  Theorem 1.

For any $n\geq 3$ and $\mathsf{e}\geq 3$,
$\mathsf{AS}_{\mathrm{LeftIns}}(\mathsf{e},n)\leq\mathsf{e}-1$.

###  3.2 Lower bound for $\mathsf{AS}_{\mathrm{LeftIns}}(\mathsf{e},n)$ on
CDAWGs

The next lower bound for $\mathsf{AS}_{\mathrm{LeftIns}}(\mathsf{e},n)$ holds
(see Appendix A.1 for a proof).

######  Theorem 2.

There exists a family of strings $T$ such that
$\mathsf{e}(T^{\prime})-\mathsf{e}(T)=\mathsf{e}(T)-2$, where $T^{\prime}=bT$
with $b\in\Sigma$. Therefore
$\mathsf{AS}_{\mathrm{LeftIns}}(\mathsf{e},n)\geq\mathsf{e}-2$.

##  4 Sensitivity of CDAWGs with left-end deletions

In this section we investigate the worst-case additive sensitivity
$\mathsf{AS}_{\mathrm{LeftDel}}(\mathsf{e},n)$ of $\mathsf{CDAWG}(T)$ when
$T[1]$ is deleted from the original input string $T$ of length $n$.

###  4.1 Upper bound for $\mathsf{AS}_{\mathrm{LeftDel}}(\mathsf{e},n)$ on
CDAWGs

Let $a=T[1]$ be the first character of string $T$. Let $T=aS$ and
$T^{\prime}=S$, and we consider left-end deletion $aS\Rightarrow S$. Since
deleting the left-end character from $T$ never increases the right-contexts of
any substring in $S$, it suffices for us to consider
$\mathsf{f}_{\mathrm{Del}}(T)=\mathsf{f}_{\mathrm{Del}}(aS)$, the total out-
degrees of new nodes that appear in
$\mathsf{CDAWG}(T^{\prime})=\mathsf{CDAWG}(S)$, namely
$\mathsf{e}(S)-\mathsf{e}(aS)\leq\mathsf{f}_{\mathrm{Del}}(aS)$.

Let $x$ be a new node in $\mathsf{CDAWG}(S)$. We have the following:

######  Lemma 7.

If $x\notin\mathsf{M}(aS)$ and $x\in\mathsf{M}(S)$, then
$x\in\mathsf{Prefix}(S)$ and $ax\in\mathsf{M}(aS)$. Also,
$\mathsf{d}_{S}(x)=\mathsf{d}_{aS}(ax)$.

  * Proof. Since $x\notin\mathsf{M}(aS)$, $x$ is either not left-maximal or not right-maximal in $aS$. If $x$ is not right-maximal in $aS$, then $x$ is also not right-maximal in $S$, hence $x\notin\mathsf{M}(S)$. However, this contradicts the precondition $x\in\mathsf{M}(S)$. Thus $x$ is not left-maximal in $aS$. Then, there exists a non-empty unique string $\alpha\in\Sigma^{+}$ such that $\alpha x=\mathsf{long}([{x}]^{\mathrm{L}}_{aS})$, which means that any occurrence of $x$ in $aS$ is immediately preceded by $\alpha$. Assume on the contrary that $x\notin\mathsf{Prefix}(S)$. Since $x\in\mathsf{M}(S)$, $x=\mathsf{long}([{x}]^{\mathrm{L}}_{S})=\mathsf{long}([{x}]^{\mathrm{L}}_{aS})$, however, this contradicts that $\alpha$ is a non-empty string. Thus $x\in\mathsf{Prefix}(S)$, and hence $ax\in\mathsf{Prefix}(aS)$. Since $ax\in\mathsf{Prefix}(aS)$ and $x$ is right-maximal in $aS$, $ax$ is a maximal string of $aS$. Thus $ax\in\mathsf{M}(aS)$.

Since $x$ is not left-maximal in $aS$ and since $ax\in\mathsf{Prefix}(aS)$,
$\mathsf{EndPos}(ax,aS)=\mathsf{EndPos}(x,aS)=\mathsf{EndPos}(x,S)$. This
leads to $\mathsf{d}_{aS}(ax)=\mathsf{d}_{S}(x)$. ∎

By Lemma 7, the out-degree of each new node in $\mathsf{CDAWG}(S)$ does not
exceed the maximum out-degree of $\mathsf{CDAWG}(aS)$. Also by Lemma 7, there
is an injective mapping from a new node $x$ in $\mathsf{CDAWG}(S)$ to an
existing node $ax$ in $\mathsf{M}(aS)\setminus\\{\varepsilon\\}$. Since
$\mathsf{d}_{aS}(\varepsilon)=\sigma\geq 2$, it holds that $\mathsf{e}(S)\leq
2(\mathsf{e}(T)-\sigma)+\sigma\leq 2\mathsf{e}(aS)-2$, that is:

######  Theorem 3.

For any $n$, $\mathsf{AS}_{\mathrm{LeftDel}}(\mathsf{e},n)\leq\mathsf{e}-2$.

###  4.2 Lower bound for $\mathsf{AS}_{\mathrm{LeftDel}}(\mathsf{e},n)$ on
CDAWGs

The next lower bound for $\mathsf{AS}_{\mathrm{LeftDel}}(\mathsf{e},n)$ holds
(see Appendix A.2 for a proof).

######  Theorem 4.

There exists a family of strings $T$ such that
$\mathsf{e}(S)-\mathsf{e}(T)=\mathsf{e}(T)-4$, where $T=aS$ with $a\in\Sigma$.
Therefore $\mathsf{AS}_{\mathrm{LeftDel}}(\mathsf{e},n)\geq\mathsf{e}-4$.

##  5 Sensitivity of CDAWGs with left-end substitutions

We consider the worst-case additive sensitivity
$\mathsf{AS}_{\mathrm{LeftSub}}(\mathsf{e},n)$ of $\mathsf{CDAWG}(T)$ when
$T[1]$ is substituted by a new character $b\neq T[1]$, i.e.
$T^{\prime}=bT[2..n]$.

###  5.1 Upper bound for $\mathsf{AS}_{\mathrm{LeftSub}}(\mathsf{e},n)$ on
CDAWGs

Similarly to the case of insertions, we separate
$\mathsf{e}(T^{\prime})-\mathsf{e}(T)$ into the two following components
$\mathsf{f}_{\mathrm{Sub}}(T)$ and $\mathsf{g}_{\mathrm{Sub}}(T)$ such that

  * •

$\mathsf{f}_{\mathrm{Sub}}(T)$ is the total out-degrees of new nodes that
appear in $\mathsf{CDAWG}(T^{\prime})$;

  * •

$\mathsf{g}_{\mathrm{Sub}}(T)$ is the total number of new out-going edges of
nodes that already exist in $\mathsf{CDAWG}(T)$.

We regard a substitution as a sequence of a deletion and an insertion, i.e.
two consecutive edit operations such that $aS~{}(=T)\Rightarrow S\Rightarrow
bS~{}(=bT[2..n]=T^{\prime})$.

####  5.1.1 $\mathsf{f}_{\mathrm{Sub}}(T)$: total out-degrees of new nodes.

Let $u$ be a new node in $\mathsf{CDAWG}(bS)$ that does not exist in
$\mathsf{CDAWG}(aS)$, namely $u\in\mathsf{M}(bS)$ and $u\notin\mathsf{M}(aS)$.
We categorize each new node $u$ to the two following types $u_{1}$ and $u_{2}$
as:

  1. 1.

$u_{1}\in\mathsf{M}(T)$ so that $u_{1}$ is generated by deletion
$aS\Rightarrow S$;

  2. 2.

$u_{2}\notin\mathsf{M}(T)$ so that $u_{2}$ is generated by insertion
$S\Rightarrow bS$.

Node $u_{1}$ is a new node that appears in $\mathsf{CDAWG}(S)$. Thus, it
follows from Lemma 7 that node $au_{1}$ exists in $\mathsf{CDAWG}(aS)$. Since
$u_{2}$ is not a node in $\mathsf{CDAWG}(S)$, it follows from Lemma 1 that
$u_{2}=bx$ and $x$ is a node in $\mathsf{CDAWG}(S)$. Based on the this
observation, we will show that there is an injective mapping from the new
nodes in $\mathsf{CDAWG}(bS)=\mathsf{CDAWG}(T^{\prime})$ to the existing nodes
in $\mathsf{CDAWG}(aS)=\mathsf{CDAWG}(T)$. In so doing, we must resolve the
two non-injective situations where:

  1. (i)

a new node $bx$ is generated by insertion $S\Rightarrow bS$, where $x$ is
generated by deletion $aS\Rightarrow S$ and $x$ remains as a node in
$\mathsf{CDAWG}(bS)$;

  2. (ii)

a new node $bax$ generated by insertion $S\Rightarrow bS$, where $x$ is
generated by deletion $aS\Rightarrow S$ and $x$ remains as a node in
$\mathsf{CDAWG}(bS)$.

Suppose (on the contrary) that Case (i) happens. Then, a new node $x$ is
generated from an existing node $ax$, and $bx$ is generated from $x$.
Therefore, two new nodes could be generated from on existed node
$ax\in\mathsf{M}(aS)$. However, the next lemma shows that this situation (Case
(i)) does not occur unless $x=S$:

######  Lemma 8.

If $x\neq S$, $x\notin\mathsf{M}(aS)$, $x\in\mathsf{M}(S)$, and
$x\in\mathsf{M}(bS)$, then $bx\notin\mathsf{M}(bS)$.

  * Proof. Since $x\notin M(aS)$ and $x\in M(S)$, $x\in\mathsf{Prefix}(S)$ by Lemma 7. Since $x\in\mathsf{M}(S)$ and $ax\in\mathsf{Prefix}(aS)$, $ax\equiv^{\mathrm{L}}_{aS}x$ and $ax=\mathsf{long}([{x}]^{\mathrm{L}}_{aS})$. This means that $bx$ occurs exactly once in $bS$ as a proper prefix. Thus, $bx\notin\mathsf{RightM}(bS)$ which leads to $bx\notin\mathsf{M}(bS)$. ∎

As for Lemma 8, the situation (Case (i)) can occur if $x=S$. However, if
$x=S$, then $S\in\mathsf{M}(bS)$ which implies that $S$ occurs in $bS$ as
prefix $bS[1..(n-1)]$. Thus, $S=b^{n}$, $T=aS=ab^{n}$ and
$T^{\prime}=bS=b^{n+1}$. It is clear that $\mathsf{e}(aS)=\mathsf{e}(bS)=n+1$.
Therefore the size of the CDAWG does not change when $x=S$.

Now we turn our attention to Case (ii) and assume (on the contrary) that it
happens. Then, two new nodes $bax$ and $x$ could be generated from a single
existing node $ax$. According to the following lemma, however, this situation
cannot occur:

######  Lemma 9.

If $ax\in\mathsf{M}(aS)$, $x\notin\mathsf{M}(aS)$, $bax\notin\mathsf{M}(aS)$,
$x\in\mathsf{M}(S)$, and $bax\notin\mathsf{M}(S)$, then
$bax\notin\mathsf{M}(bS)$.

  * Proof. Assume on the contrary that $bax\in\mathsf{M}(bS)$. Since $x\notin M(aS)$ and $x\in M(S)$, $x\in\mathsf{Prefix}(S)$ by Lemma 7. Also, since $bax\notin M(S)$ and $bax\in M(bS)$, $ax\in\mathsf{Prefix}(S)$ by Lemma 1. This means that $x\in\mathsf{Prefix}(ax)$ and $x=a^{|x|}$. Since $ax=a^{|x|+1}$ is a maximal substring of $aS$, $x$ is also a maximal substring of $aS$. Thus $x\in\mathsf{M}(aS)$, however, this contradicts the precondition that $x\notin\mathsf{M}(aS)$. Thus $bax\notin\mathsf{M}(bS)$. ∎

As a result, there is an injective mapping from the new nodes $u_{1}$ (resp.
$u_{2}=bx$) in $\mathsf{CDAWG}(bS)$ to the existing nodes $au_{1}$ (resp. $x$)
in $\mathsf{CDAWG}(aS)$ by Lemmas 1, 7, 8, and 9. It also follows from these
lemmas that the out-degree of each new node in $\mathsf{CDAWG}(bS)$ does not
exceed the maximum out-degree of $\mathsf{CDAWG}(aS)$. Finally, we consider
the source $\varepsilon$. By Lemmas 2, 3, and 7, if $b\in\mathsf{M}(bS)$,
$b\notin\mathsf{M}(aS)$, and $\mathsf{e}(aS)\geq 3$, then
$\mathsf{d}_{bS}(b)\leq\mathsf{d}_{aS}(\varepsilon)$. Thus we have:

######  Lemma 10.

For any string $T$ with $\mathsf{e}(T)\geq 3$,
$\mathsf{f}_{\mathrm{Sub}}(T)\leq\mathsf{e}(T)-1$.

####  5.1.2 $\mathsf{g}_{\mathrm{Sub}}(T)$: number of new branches from
existing nodes.

Since left-end deletions do not create new branches from existing nodes
(recall Section 4), it is immediate from Lemma 5 that:

######  Lemma 11.

For any string $T$, $\mathsf{g}_{\mathrm{Sub}}(T)\leq 1$.

####  5.1.3 Wrapping up.

Our main result of this section follows from Lemmas 10 and 11:

######  Theorem 5.

For any $n\geq 4$ and $\mathsf{e}\geq 3$,
$\mathsf{AS}_{\mathrm{LeftSub}}(\mathsf{e},n)\leq\mathsf{e}$.

###  5.2 Lower bound for $\mathsf{AS}_{\mathrm{LeftSub}}(\mathsf{e},n)$ on
CDAWGs

The next lower bound for $\mathsf{AS}_{\mathrm{LeftSub}}(\mathsf{e},n)$ holds
(see Appendix A.3 for a proof).

######  Theorem 6.

There exists a family of strings $T$ such that
$\mathsf{e}(T^{\prime})-\mathsf{e}(T)=\mathsf{e}(T)-3$, where
$T^{\prime}=bT[2..n]$ with $b\in\Sigma\setminus\\{T[1]\\}$. Therefore
$\mathsf{AS}_{\mathrm{LeftSub}}(\mathsf{e},n)\geq\mathsf{e}-3$.

##  6 Quadratic-time bound for leftward online construction

The leftward online construction problem for the CDAWG is, given a string $T$
of length $n$, to maintain $\mathsf{CDAWG}(T[i..n])$ for decreasing
$i=n,\ldots,1$. By extending our lower bound on the sensitivity with left-end
insertions/deletions, a quadratic bound for this online CDAWG construction
follows:

######  Theorem 7.

There exists a family of strings $T_{m}$ for which the total work for building
$\mathsf{CDAWG}(T_{m}[i..n])$ for decreasing $i=n,\ldots,1$ is
$\Omega(n^{2})$, where $n=|T_{m}|$.

Figure 2: Illustration for the CDAWGs of strings
$T_{k,m}=(ab)^{3}cab(ab)^{4}\$$, $bT_{k,m}=b(ab)^{3}cab(ab)^{4}\$$, and
$T_{k+1,m}=(ab)^{4}cab(ab)^{4}\$$ with $k=1,m=2$.

  * Proof. Consider string $T_{m}=(ab)^{2m}cab(ab)^{2m}\$$, where $a,b,c,\$\in\Sigma$. For $0\leq k\leq m$, let $T_{k,m}$ denote a series of suffixes of $T_{m}$ such that $T_{k,m}=(ab)^{m+k}cab(ab)^{2m}\$$. Notice $T_{m,m}=T_{m}$, $m=\Theta(n)$ with $n=|T_{m,m}|$, and $T_{k,m}=T_{m}[2(m-k)+1..n]$.

Now, we consider building $\mathsf{CDAWG}(T_{m}[i..n])$ for decreasing
$i=n,\ldots,1$, and suppose we have already built $\mathsf{CDAWG}(T_{k,m})$.
For this string $T_{k,m}$, we have that
$\mathsf{M}(T_{k,m})=\\{\varepsilon,ab,(ab)^{2},\ldots,(ab)^{2m},T_{k,m}\\}$.
For any node $v$ of
$\mathsf{CDAWG}(T_{k,m})=(\mathsf{V}_{T_{k,m}},\mathsf{E}_{T_{k,m}})$, let
$\mathsf{d}_{T_{k,m}}(v)$ denote the out-degree of $v$. Then, since
$\mathsf{d}_{T_{k,m}}(\varepsilon)=4$, $\mathsf{d}_{T_{k,m}}((ab)^{i})=3$ for
every $1\leq i\leq m+k$, $\mathsf{d}_{T_{k,m}}((ab)^{j})=2$ for every
$m+k+1\leq j\leq 2m$, and $\mathsf{d}_{T_{k,m}}(T_{k,m})=0$. Therefore
$\mathsf{e}(T_{k,m})=5m+k+4$.

Let us now prepend character $b$ to $T_{k,m}$ and obtain
$T_{k+1,m}=bT_{k,m}=b(ab)^{m+k}c(ab)^{2m}\$$. It is clear that
$bT_{k,m}=T_{m,m}[2(m-k)..n]$. We have that

$\displaystyle\mathsf{M}(bT_{k,m})$ $\displaystyle=$
$\displaystyle\\{\varepsilon,ab,(ab)^{2},...,(ab)^{2m},b,bab,b(ab)^{2},...,b(ab)^{m+k},bT_{k,m}\\}$
$\displaystyle=$
$\displaystyle\left(\mathsf{M}(T_{k,m})\setminus\\{T_{k,m}\\}\right)\cup\\{b,bab,b(ab)^{2},...,b(ab)^{m+k}\\}\cup\\{bT_{k,m}\\},$

and that $\mathsf{d}_{bT_{k,m}}(\varepsilon)=4$, $\mathsf{d}_{bT_{k,m}}(b)=3$,
$\mathsf{d}_{bT_{k,m}}((ab)^{i})=\mathsf{d}_{bT_{k,m}}(b(ab)^{i})=3$ for every
$1\leq i\leq m+k$, $\mathsf{d}_{bT_{k,m}}(b(ab)^{j})=2$ for every $m+k+1\leq
j\leq 2m$, and $\mathsf{d}_{bT_{k,m}}(bT_{k,m})=0$. Thus
$\mathsf{e}(bT_{k,m})=8m+4k+7$. Therefore, building
$\mathsf{CDAWG}(T_{k+1,m})$ from $\mathsf{CDAWG}(T_{k,m})$ requires to _add_
$|\mathsf{e}(T_{k+1,m})-\mathsf{e}(T_{k,m})|=3m+3k+3=\Omega(m)$ new edges (see
the first step of Fig. 2 for illustration).

Let us move on to the next step, where we prepend character $a$ to $bT_{k,m}$
and obtain $T_{k+1,m}=abT_{k,m}=ab(ab)^{m+k}c(ab)^{2m}\$$. Note that
$abT_{k,m}=T_{k+1,m}=T_{m}[2(m-k)-1..n]$, and
$\mathsf{M}(T_{k+1,m})=\\{\varepsilon,ab,(ab)^{2},...,(ab)^{2m},T_{k+1,m}\\}$.
We also have $\mathsf{d}_{T_{k+1,m}}(\varepsilon)=4$,
$\mathsf{d}_{T_{k+1,m}}((ab)^{i})=3$ for every $1\leq i\leq m+k+1$,
$\mathsf{d}_{T_{k+1,m}}((ab)^{j})=2$ for every $m+k+2\leq j\leq 2m$, and
$\mathsf{d}_{T_{k+1,m}}(T_{k+1,m})=0$. This leads to
$\mathsf{e}(T_{k+1,m})=5m+k+5$. Therefore, building
$\mathsf{CDAWG}(T_{k+1,m})$ from $\mathsf{CDAWG}({bT_{k,m}})$ requires to
_remove_ $|\mathsf{e}(T_{k+1,m})-\mathsf{e}(bT_{k,m})|=3m+3k+2=\Omega(m)$
existing edges (see the second step of Fig. 2 for illustration).

This process of adding and removing $\Omega(m)$ edges in every two steps
repeats when we update $\mathsf{CDAWG}(T_{k,m})$ to
$\mathsf{CDAWG}(T_{k+1,m})$ for every increasing $k=1,\ldots,m-1$. Since
$m=\Theta(n)$, the total work for building $\mathsf{CDAWG}(T_{m}[i..n])$ for
decreasing $i=n,\ldots,1$ is $\Omega(m^{2})=\Omega(n^{2})$. ∎

######  Remark 1.

The linear-time algorithm of [8] for _rightward_ online CDAWG construction
maintains a slightly modified version of the CDAWG, which becomes isomorphic
to our CDAWG when a terminal symbol $\$$ is appended to the string. Still, our
lower bound instance from Theorem 7 shows that $\$$ does not help improve the
time complexity of _leftward_ online CDAWG construction.

##  7 Conclusions and further work

This paper investigated the worst-case additive sensitivity of the size of
CDAWGs when a single-character edit operation is performed on the left-end of
the input string. We proved that the number of new edges that appear after a
left-end edit operation is at most the number of existing edges (upper bound).
We also showed that there are almost matching lower bounds for all cases of
left-end insertions, deletions, and substitutions.

An apparent future work is to close the small gap between our upper and lower
bounds, which is at most by an additive factor of 3 (recall Table 1).

Another intriguing open question is the sensitivity of CDAWGs when an edit
operation can be performed at an arbitrary position in the string. Our left-
end sensitivity results should partly contribute to the general case, since
maximal repeats that touch the edited position can be analyzed in a similar
way. What remains is how to deal with maximal repeats which contain the edited
position.

## Acknowledgements

The authors thank Mitsuru Funakoshi for discussions. This work was supported
by KAKENHI grant numbers 21K17705 and 22H03551.

## References

  * [1] T. Akagi, M. Funakoshi, and S. Inenaga.  Sensitivity of string compressors and repetitiveness measures.  Information and Computation, 291:104999, 2023.
  * [2] D. Belazzougui and F. Cunial.  Fast label extraction in the CDAWG.  In SPIRE 2017, pages 161–175, 2017.
  * [3] D. Belazzougui, F. Cunial, T. Gagie, N. Prezza, and M. Raffinot.  Composite repetition-aware data structures.  In CPM 2015, pages 26–39, 2015.
  * [4] A. Blumer, J. Blumer, D. Haussler, R. McConnell, and A. Ehrenfeucht.  Complete inverted files for efficient text retrieval and analysis.  Journal of the ACM, 34(3):578–595, 1987.
  * [5] M. Burrows and D. J. Wheeler.  A block sorting lossless data compression algorithm.  Technical Report 124, Digital Equipment Corporation, 1994.
  * [6] M. Crochemore and R. Vérin.  On compact directed acyclic word graphs.  In Structures in Logic and Computer Science: A Selection of Essays in Honor of A. Ehrenfeucht, pages 192–211. Springer, 1997.
  * [7] H. Fujimaru, Y. Nakashima, and S. Inenaga.  On sensitivity of compact directed acyclic word graphs.  CoRR, abs/2303.01726, 2023.
  * [8] S. Inenaga, H. Hoshino, A. Shinohara, M. Takeda, S. Arikawa, G. Mauri, and G. Pavesi.  On-line construction of compact directed acyclic word graphs.  Discrete Applied Mathematics, 146(2):156–179, 2005.
  * [9] D. Kempa and N. Prezza.  At the roots of dictionary compression: string attractors.  In STOC 2018, pages 827–840, 2018.
  * [10] T. Kociumaka, G. Navarro, and N. Prezza.  Towards a definitive measure of repetitiveness.  In LATIN 2020, pages 207–219, 2020.
  * [11] J. Radoszewski and W. Rytter.  On the structure of compacted subword graphs of Thue-Morse words and their applications.  J. Discrete Algorithms, 11:15–24, 2012.
  * [12] M. Senft and T. Dvorák.  Sliding CDAWG perfection.  In SPIRE 2008, pages 109–120, 2008.
  * [13] T. Takagi, K. Goto, Y. Fujishige, S. Inenaga, and H. Arimura.  Linear-size CDAWG: New repetition-aware indexing and grammar compression.  In SPIRE 2017, pages 304–316, 2017.
  * [14] M. Takeda, T. Matsumoto, T. Fukuda, and I. Nanri.  Discovering characteristic expressions from literary works: a new text analysis method beyond n-gram statistics and KWIC.  In Discovery Science 2000, pages 112–126, 2000.
  * [15] P. Weiner.  Linear pattern matching algorithms.  In Proceedings of the 14th Annual Symposium on Switching and Automata Theory, pages 1–11. IEEE, 1973.
  * [16] J. Ziv and A. Lempel.  A universal algorithm for sequential data compression.  IEEE Transactions on Information Theory, 23(3):337–343, 1977.

##  Appendix A Appendix: Lower bounds on sensitivity of CDAWGs with left-end
edits

We present infinite families of strings that exhibit almost tight lower bounds
on the worst-case additive sensitivity of CDAWGs with left-end edit
operations.

###  A.1 Proof for Lemma 2 (left-end insertions)

  * Proof. Consider string $T=(ab)^{m}c(ab)^{m+1}$, where $a,b,c\in\Sigma$. We have that

$\mathsf{M}(T)=\\{\varepsilon,ab,(ab)^{2},...,(ab)^{m},T\\}.$

Then, since $\mathsf{d}_{T}(\varepsilon)=3$, $\mathsf{d}_{T}((ab)^{i})=2$ for
every $1\leq i\leq m$, and $\mathsf{d}_{T}(T)=0$, we have
$\mathsf{e}(T)=2m+3$.

Let us now prepend character $b$ to $T$ and obtain
$T^{\prime}=b(ab)^{m}c(ab)^{m+1}$. We have that

$\displaystyle\mathsf{M}(T^{\prime})$ $\displaystyle=$
$\displaystyle\\{\varepsilon,ab,(ab)^{2},...,(ab)^{m},b,bab,b(ab)^{2},...,b(ab)^{m},T^{\prime}\\}$
$\displaystyle=$
$\displaystyle\left(\mathsf{M}(T)\setminus\\{T\\}\right)\cup\\{b,bab,b(ab)^{2},...,b(ab)^{m}\\}\cup\\{T^{\prime}\\},$

and that $\mathsf{d}_{T^{\prime}}(\varepsilon)=3$,
$\mathsf{d}_{T^{\prime}}((ab)^{i})=2$ for every $1\leq i\leq m$,
$\mathsf{d}_{T^{\prime}}(b(ab)^{i})=2$ for every $0\leq i\leq m-1$,
$\mathsf{d}_{T^{\prime}}(b(ab)^{m})=1$, and
$\mathsf{d}_{T^{\prime}}(T^{\prime})=0$ (see Fig. 3 for illustration). Thus
$\mathsf{e}(T^{\prime})=4m+4=2(2m+3)-2=2\mathsf{e}(T)-2$ which shows the claim
$\mathsf{AS}_{\mathrm{LeftIns}}(\mathsf{e},n)\geq\mathsf{e}-2$. ∎

Figure 3: Illustration for the CDAWGs of strings $T=(ab)^{3}cab(ab)^{3}$ and
$T^{\prime}=bT=b(ab)^{3}cab(ab)^{3}$ with $m=3$. The omitted edge labels are
all $c(ab)^{4}$. Observer that $\mathsf{e}(T)=9$ and
$\mathsf{e}(T^{\prime})=16$, and hence
$\mathsf{e}(T^{\prime})-\mathsf{e}(T)=7=\mathsf{e}(T)-2$ with this left-end
insertion.

###  A.2 Proof for Theorem 4 (left-end deletions)

  * Proof. Consider string $T=(ab)^{m+1}c(ab)^{m}$, where $a,b,c\in\Sigma$. We have that

$\mathsf{M}(T)=\\{\varepsilon,ab,(ab)^{2},...,(ab)^{m},T\\}.$

Then, since $\mathsf{d}_{T}(\varepsilon)=3$, $\mathsf{d}_{T}((ab)^{i})=2$ for
every $1\leq i\leq m$, and $\mathsf{d}_{T}(T)=0$, we have
$\mathsf{e}(T)=2m+3$.

Let us now deleted the first character $a=T[1]$ from $T$ and obtain
$T^{\prime}=b(ab)^{m}c(ab)^{m}$. We have that

$\displaystyle\mathsf{M}(T^{\prime})$ $\displaystyle=$
$\displaystyle\\{\varepsilon,ab,(ab)^{2},...,(ab)^{m},b,bab,b(ab)^{2},...,b(ab)^{m-1},T^{\prime}\\}$
$\displaystyle=$
$\displaystyle\left(\mathsf{M}(T)\setminus\\{T\\}\right)\cup\\{b,bab,b(ab)^{2},...,b(ab)^{m-1}\\}\cup\\{T^{\prime}\\},$

and that $\mathsf{d}_{T^{\prime}}(\varepsilon)=3$,
$\mathsf{d}_{T^{\prime}}((ab)^{i})=2$ for every $1\leq i\leq m-1$,
$\mathsf{d}_{T^{\prime}}(b(ab)^{i})=2$ for every $0\leq i\leq m-1$,
$\mathsf{d}_{T^{\prime}}((ab)^{m})=1$, and
$\mathsf{d}_{T^{\prime}}(T^{\prime})=0$ (see Fig. 4 for illustration). Thus
$\mathsf{e}(T^{\prime})=4m+2=2(2m+3)-4=2\mathsf{e}(T)-4$ which shows the claim
that $\mathsf{AS}_{\mathrm{LeftDel}}(\mathsf{e},n)\geq\mathsf{e}-4$. ∎

Figure 4: Illustration for the CDAWGs of strings $T=(ab)^{4}abc(ab)^{3}$ and
$T^{\prime}=T[2..n]=b(ab)^{3}c(ab)^{3}$ with $m=3$. The omitted edge labels
are all $c(ab)^{3}$. Observe that $\mathsf{e}(T)=9$,
$\mathsf{e}(T^{\prime})=14$, and hence
$\mathsf{e}(T^{\prime})-\mathsf{e}(T)=5=\mathsf{e}(T)-4$ with this left-end
deletion.

###  A.3 Proof for Theorem 6 (left-end substitutions)

  * Proof. Consider string $T=(ab)^{m+1}c(ab)^{m}$, where $a,b,c\in\Sigma$. We have that

$\mathsf{M}(T)=\\{\varepsilon,ab,(ab)^{2},...,(ab)^{m},T\\}.$

Then, since $\mathsf{d}_{T}(\varepsilon)=3$, $\mathsf{d}_{T}((ab)^{i})=2$ for
every $1\leq i\leq m$, and $\mathsf{d}_{T}(T)=0$, we have
$\mathsf{e}(T)=2m+3$.

Let us now replace the first character $a=T[1]$ of $T$ by $b$ and obtain
$T^{\prime}=bb(ab)^{m}c(ab)^{m}$. We have that

$\displaystyle\mathsf{M}(T^{\prime})$ $\displaystyle=$
$\displaystyle\\{\varepsilon,ab,(ab)^{2},...,(ab)^{m},b,bab,b(ab)^{2},...,b(ab)^{m-1},T^{\prime}\\}$
$\displaystyle=$
$\displaystyle\left(\mathsf{M}(T)\setminus\\{T\\}\right)\cup\\{b,bab,b(ab)^{2},...,b(ab)^{m-1}\\}\cup\\{T^{\prime}\\},$

and that $\mathsf{d}_{T^{\prime}}(\varepsilon)=\mathsf{d}_{T^{\prime}}(b)=3$,
$\mathsf{d}_{T^{\prime}}((ab)^{i})=\mathsf{d}_{T^{\prime}}(b(ab)^{i})=2$ for
every $1\leq i\leq m-1$, $\mathsf{d}_{T^{\prime}}(b(ab)^{m})=1$, and
$\mathsf{d}_{T^{\prime}}(T^{\prime})=0$ (see Fig. 5 for illustration). Thus
$\mathsf{e}(T^{\prime})=4m+3=2(2m+3)-3=2\mathsf{e}(T)-3$ which shows the claim
that $\mathsf{AS}_{\mathrm{LeftSub}}(\mathsf{e},n)\geq\mathsf{e}-3$. ∎

Figure 5: Illustration for the CDAWGs of strings $T=(ab)^{4}c(ab)^{3}$ and
$T^{\prime}=bT[2..n]=bb(ab)^{3}c(ab)^{3}$ with $m=3$. The omitted edge labels
are all $c(ab)^{3}$. Observe that $\mathsf{e}(T)=9$,
$\mathsf{e}(T^{\prime})=15$, and hence
$\mathsf{e}(T^{\prime})-\mathsf{e}(T)=6=\mathsf{e}(T)-3$ with this left-end
deletion.