Constant Multiplicative Sensitivity on the CDAWGs

Hamai, Rikuya; Fujimaru, Hiroto; Inenaga, Shunsuke

doi:10.4230/LIPIcs.CPM.2026.8

Constant Multiplicative Sensitivity on the CDAWGs

Rikuya Hamai

Department of Information Science and Technology, Kyushu University, Fukuoka, Japan Hiroto Fujimaru

Department of Information Science and Technology, Kyushu University, Fukuoka, Japan Shunsuke Inenaga

Department of Informatics, Kyushu University, Fukuoka, Japan

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$ , and thus CDAWGs are a compact indexing structure. Indeed, the CDAWG size $\mathsf{e}$ can be sublinear in $n$ for some highly repetitive strings. Of its various applications, the CDAWG allows for computing pattern occurrences, maximal exact matches (MEMs), minimal absent words (MAWs), and minimal unique substrings (MUSs) in optimal time using $O(\mathsf{e})$ space. For designing space-efficient data storage, it is crucial that the underlying data structure is robust against data edits and errors. As a mathematical measure for this, the notion of compression sensitivity [Akagi et al. 2023] was introduced as the maximum of the size increase in the compressed data structures after edits operations. In this paper, we investigate the sensitivity of CDAWGs when a single character edit operation is performed at an arbitrary position in the input string $T$ . We show that the size of the CDAWG after an edit operation on $T$ is asymptotically at most 8 times larger than the original CDAWG before the edit. This $O(1)$ upper bound significantly improves on the only known upper bound $O(n/\log n)$ for the problem.

Keywords and phrases:

string data structures, maximal repeats, data compression, compression sensitivity, CDAWGs

Funding:

Rikuya Hamai: JST BOOST Grant Number JPMJBS2406.

Hiroto Fujimaru: JST BOOST Grant Number JPMJBS2406.

Shunsuke Inenaga: JSPS KAKENHI Grant Numbers JP23K24808 and JP23K18466.

Copyright and License:

2012 ACM Subject Classification:

Mathematics of computing

\rightarrow

Combinatorial algorithms

DOI:

10.4230/LIPIcs.CPM.2026.8

Event:

37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026)

Editors:

Philip Bille and Nicola Prezza

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Compact directed acyclic word graphs (CDAWGs) [4] 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$ (denoted $\mathsf{CDAWG}(T)$ ) is a minimal partial DFA that is obtained by merging isomorphic subtrees of the suffix tree [30] of the same string $T$ . Let $\mathsf{e}$ denote the size (i.e. the number of edges) of the CDAWG for the input string. It is known that $\mathsf{e}\leq 2n-2$ holds [4] for any strings of length $n$ , and $\mathsf{e}$ can be sublinear in $n$ for some highly repetitive strings [27, 2, 25]. CDAWGs can thus be regarded as a compressed text indexing structure, which can be stored in $O(\mathsf{e})$ space without explicitly storing the string [3, 14]. A grammar-based string compression of size $O(\mathsf{e})$ is also known [3, 7].

Given a pattern $P$ of length $m$ , the CDAWG of text $T$ permits exact pattern matching in optimal $O(m+occ)$ time with $O(\mathsf{e})$ space, where $o c c$ is the number of occurrences of $P$ in $T$ . By adapting the suffix-tree based approach (Algorithm 1 in [23]), inexact matches such as exact maximal matches (MEMs) and generalized MEMs ( $k$ -MEMs and $k$ -rare MEMs) can also be computed in optimal $O(m)$ time and with $O(\mathsf{e})$ space by the CDAWG. Finding (generalized) MEMs has important applications in bioinformatics. CDAWGs are also used as a space-efficient data structure allowing for optimal-time detection of “unusual words” (such as minimal absent words (MAWs) [8], minimal unique substrings (MUSs) [13]), and string net occurrences [12] from the input string with $O(\mathsf{e})$ space each [3, 16, 20]. On a more practical side, CDAWGs enjoy applications in natural language processing [29] and in analysis of text generated by language models (LMs) [19].

In this paper, we consider the multiplicative sensitivity of the CDAWG size $\mathsf{e}$ which is defined by the worst-case value of $\mathsf{e}(T^{\prime})/\mathsf{e}(T)$ , where $T$ is the input string and $T^{\prime}$ is a string obtained by performing a single-character edit operation on $T$ . In case where the edit operation to the string $T$ is performed at either end of $T$ , then the multiplicative sensitivity of CDAWGs is known to be asymptotically at most $2$ , and it is tight [15, 9]. However, the general case with an arbitrary single-character-wise edit on $T$ was not well understood for CDAWGs. In this paper, we prove that any edit operation at an arbitrary position on the string can increase the size of the CDAWG asymptotically at most 8 times larger than the original. We emphasize that the only known upper bound for the sensitivity of CDAWGs is $O(n/\log n)$ , which trivially follows since $\mathsf{e}\in O(n)$ and $\mathsf{e}\in\Omega(\log n)$ for any string of length $n$ [4, 3]. Our technique for proving the constant sensitivity of CDAWGs is purely combinatorial, which involves new and original ideas that were not present in the special case of left/right-end edits [15, 9].

Compression sensitivity.

Following the earlier work of Lagarde and Perifel [18] and Akagi et al. [1], string compressors and repetitiveness measures can be categorized into three classes:

(A)

Stable: Those whose multiplicative sensitivity is $O(1)$ ;
(B)

Changeable: Those whose multiplicative sensitivity is $\mathrm{polylog}(n)$ ;
(C)

Catastrophic: Those whose multiplicative sensitivity is $O(n^{c})$ with some constant $0<c\leq 1$ .

To mention a few of them, it is shown in [1] that Class (A) includes the substring complexity [17], the smallest macro scheme [28], the Lempel-Ziv 77 families [31, 28], and the smallest grammar [26, 6]. Our new result implies that the CDAWGs belong to Class (A). Class (B) includes run-length Burrows-Wheeler transform (RLBWT) as shown in [1, 10, 11], and lex-parse [24] as shown by Nakashima et al. [22]. It is shown by Lagarde and Perifel [18] that the Lempel-Ziv 78 [32] belongs to Class (C).

2 Preliminaries

Strings.

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$ . For any non-negative integer $n\geq 0$ , let $\Sigma^{n}$ denote the set of strings of length $n$ . For any two strings $S$ and $T$ , let $\mathsf{ed}(S,T)$ denote the edit distance between $S$ and $T$ . For any string $T$ and a non-negative integer $\ell\geq 0$ , let $\mathcal{K}(T,\ell)=\{S\mid\mathsf{ed}(S,T)=\ell\}$ .

For string $T=uvw$ , $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$ .

Maximal substrings and maximal repeats.

A substring $w\in\mathsf{Substr}(T)$ of $T$ is left-maximal if (1) $w\in\mathsf{Prefix}(T)$ or (2) there exist two distinct characters $a,b\in\Sigma$ such that $aw,bw\in\mathsf{Substr}(T)$ , and it is right-maximal if (1) $w\in\mathsf{Suffix}(T)$ or (2) there exist two distinct characters $a,b\in\Sigma$ such that $wa,wb\in\mathsf{Substr}(T)$ . These substrings $w$ that occur at least twice in $T$ are also called left-maximal repeats and right-maximal repeats in $T$ , respectively.

Let $\mathsf{LeftM}(T)$ and $\mathsf{RightM}(T)$ denote the sets of left-maximal and right-maximal substrings in $T$ . Let $\mathsf{M}(T)=\mathsf{LeftM}(T)\cap\mathsf{RightM}(T)$ . The elements in $\mathsf{M}(T)$ are called maximal substrings in $T$ , and the elements in $\mathsf{M}(T)\setminus\{T\}$ are called maximal repeats in $T$ . A character $a\in\Sigma$ is said to be a right-extension of a maximal repeat $w$ of $T$ if $wa\in\mathsf{Substr}(T)$ .

For any substring $w$ of a string $T$ , we define its left-representation and right-representation by $\mathsf{lexp}_{T}(w)=\alpha w$ and $\mathsf{rexp}_{T}(w)=w\beta$ , where $\alpha,\beta\in\Sigma^{*}$ are the shortest strings such that $\alpha w$ is left-maximal in $T$ and $w\beta$ is right-maximal in $T$ , respectively.

CDAWG.

The compact directed acyclic word graph (CDAWG) of a string $T$ , denoted $\mathsf{CDAWG}(T)$ , is the minimal DFA that recognizes all substrings of $T$ , in which each transition (edge) is labeled by a non-empty substring of $T$ . $\mathsf{CDAWG}(T)$ has a unique source that represents the empty string $\varepsilon$ and a unique sink that represents $T$ . All the other internal nodes represent the maximal repeats in $T$ , namely, the set of the longest strings represented by the nodes of $\mathsf{CDAWG}(T)$ are equal to $\mathsf{M}(T)$ . See Figure 1 for a concrete example of CDAWGs. The size of $\mathsf{CDAWG}(T)$ for a string $T$ of length $n$ is the number $\mathsf{e}(T)$ of edges in $\mathsf{CDAWG}(T)$ , which is equal to the number of right-extensions of maximal repeats in $T$ . For each $x\in\mathsf{M}(T)$ , let $\mathsf{d}_{T}(x)$ denote the number of out-edges of node $x$ in $\mathsf{CDAWG}(T)$ . It is clear that $\mathsf{e}(T)=\sum_{x\in\mathsf{M}(T)}\mathsf{d}_{T}(x)$ . In what follows, we will identify maximal substrings with CDAWG nodes, and right-extensions of maximal repeats with CDAWG edges, respectively.

Figure 1: Illustration for

\mathsf{CDAWG}(T)

of string

T=\mathtt{(ab)^{2}c(ab)^{2}d}

. The longest strings represented by the nodes of

\mathsf{CDAWG}(T)

are the maximal substrings in

\mathsf{M}(T)=\{\mathtt{\varepsilon,ab,(ab)^{2},(ab)^{2}c(ab)^{2}d}\}

.

Sensitivity of CDAWG size and our results.

Using the measure $\mathsf{e}$ , we define the worst-case multiplicative sensitivity of the CDAWG with an edit operation (insertion, deletion, or substitution) by $\mathsf{MS}(\mathsf{\mathsf{e}},n)=\max_{T\in\Sigma^{n},T^{\prime}\in\mathcal{% K}(T,1)}\{\mathsf{e}(T^{\prime})/\mathsf{e}(T)\}$ .

In this paper, we prove the following:

Theorem 1.

For any string $T$ of length $n$ , $\mathsf{MS}(\mathsf{e},n)\leq(8\mathsf{e}+4)/\mathsf{e}$ holds. For any string $T$ of length $n$ ending with a unique character $\$$ , $\mathsf{MS}(\mathsf{e},n)\leq(5\mathsf{e}+4)/\mathsf{e}$ holds.

3 Occurrences of maximal repeats crossing the edited position

To present an upper bound for the sensitivity of CDAWG size, it is essential to consider new occurrences of maximal repeats that contain or touch the edited position $i$ . In this section, we introduce several new definitions regarding those new occurrences of maximal repeats.

Definition 2 (Crossing occurrences).

Let $x=T^{\prime}[j..k]$ be a non-empty substring of $T^{\prime}$ that touches or contains the edited position $i$ . That is, if the edit operation is insertion and substitution, (1) $k=i-1$ (touching $i$ from left), (2) $j\leq i\leq k$ (containing $i$ ), or (3) $j=i+1$ (touching $i$ from right). If the edit operation is deletion, (1) $k=i-1$ (touching $i$ from left), (2) $j\leq i-1\land i\leq k$ (containing $i$ ), or (3) $j=i$ (touching $i$ from right). These occurrences of a substring $x$ in $T^{\prime}$ are said to be crossing occurrences for the edited position $i$ . We will call these occurrences simply as crossing occurrences of $x$ .

We denote the left most crossing occurrence $T^{\prime}[j^{\prime}..k^{\prime}]$ of $x$ as $x_{L}$ . For $x_{L}$ , we consider the following substrings $P_{x_{L}}$ and $S_{x_{L}}$ of $T^{\prime}$ (see Figure 2 for illustration):

Figure 2: Illustration of

x_{L}

in

T^{\prime}

for the case where

x_{L}

contains

i

, with insertion and substitution.

In the case that the edit operation is insertion or substitution, let

	$\displaystyle P_{x_{L}}$	$\displaystyle=$	$\displaystyle\begin{cases}T^{\prime}[j^{\prime}..i]&\mbox{if $x_{L}$ touches $% i$ from left or contains $i$,}\\ \varepsilon&\mbox{if $x_{L}$ touches $i$ from right,}\end{cases}$
	$\displaystyle S_{x_{L}}$	$\displaystyle=$	$\displaystyle\begin{cases}\varepsilon&\mbox{if $x_{L}$ touches $i$ from left,}% \\ T^{\prime}[i..k^{\prime}]&\mbox{if $x_{L}$ contains $i$ or touches $i$ from % right.}\end{cases}$

In the case that the edit operation is deletion, let

	$\displaystyle P_{x_{L}}$	$\displaystyle=$	$\displaystyle\begin{cases}T^{\prime}[j^{\prime}..i-1]&\mbox{if $x_{L}$ touches% $i$ from left or contains $i$,}\\ \varepsilon&\mbox{if $x_{L}$ touches $i$ from right,}\end{cases}$
	$\displaystyle S_{x_{L}}$	$\displaystyle=$	$\displaystyle\begin{cases}\varepsilon&\hskip 17.07164pt\mbox{if $x_{L}$ % touches $i$ from left,}\\ T^{\prime}[i..k^{\prime}]&\hskip 17.07164pt\mbox{if $x_{L}$ contains $i$ or % touches $i$ from right.}\end{cases}$

We define the rightmost crossing occurrence $x_{R}$ , together with $P_{x_{R}}$ and $S_{x_{R}}$ , analogously.

Definition 3.

We categorize strings $x$ that have crossing occurrence(s) in the edited string in $T^{\prime}$ into the five following types, depending on the properties of $x$ :

Type (i):

$x$ has only one crossing occurrence of $x$ in $T^{\prime}$ .

Type (ii):

1.

$x$ has two or more crossing occurrences of $x$ in $T^{\prime}$ .
2.

If all occurrences of $x$ in $T^{\prime}$ are crossing occurrences of $x$ in $T^{\prime}$ , then $x\notin\mathsf{LeftM}(T^{\prime})$ and $x\notin\mathsf{RightM}(T^{\prime})$ .

Type (iii):

1.

$x$ has two or more crossing occurrences of $x$ in $T^{\prime}$ .
2.

If all occurrences of $x$ in $T^{\prime}$ are crossing occurrences of $x$ in $T^{\prime}$ , then $x\notin\mathsf{LeftM}(T^{\prime})$ and $x\in\mathsf{RightM}(T^{\prime})$ .

Type (iv):

1.

$x$ has two or more crossing occurrences of $x$ in $T^{\prime}$ .
2.

If all occurrences of $x$ in $T^{\prime}$ are crossing occurrences of $x$ in $T^{\prime}$ , then $x\in\mathsf{LeftM}(T^{\prime})$ and $x\notin\mathsf{RightM}(T^{\prime})$ .

Type (v):

1.

$x$ has two or more crossing occurrences of $x$ in $T^{\prime}$ .
2.

If all occurrences of $x$ in $T^{\prime}$ are crossing occurrences of $x$ in $T^{\prime}$ , then $x\in\mathsf{M}(T^{\prime})$ .

Figure 3 illustrates the five types of a string $x$ when $x_{L}\notin\mathsf{Prefix}(T^{\prime})$ and $x_{R}\notin\mathsf{Suffix}(T^{\prime})$ .

Figure 3: Illustration for the five types of a string

x

when

x_{L}\notin\mathsf{Prefix}(T^{\prime})

and

x_{R}\notin\mathsf{Suffix}(T^{\prime})

, where

a\neq c

and

b\neq d

for characters

a,b,c,d\in\Sigma

.

The reason why we only consider $x_{L}$ and $x_{R}$ is due to the periodicity for $x$ . We remark that when $x$ has multiple crossing occurrences which contain or touch the edited position $i$ in $T^{\prime}$ , then the characters immediately before all crossing occurrences of $x$ in $T^{\prime}$ except for $x_{L}$ are the same and the characters immediately after all crossing occurrences of $x$ in $T^{\prime}$ except for $x_{R}$ are the same. This is because when $x$ has three or more crossing occurrences containing $i$ in $T^{\prime}$ , then all these crossing occurrences of $x$ are periodic (c.f. [5, 21]). Therefore, to examine whether $x$ is maximal in $\mathsf{M}(T^{\prime})$ or not, we do not need to consider all crossing occurrences of $x$ in $T^{\prime}$ other than $x_{L}$ and $x_{R}$ .

In Definitions 4 and 5 below, we introduce $\mathsf{N}$ and $\mathsf{Q}$ which are respectively the sets of new maximal repeats and existing maximal repeats in $T^{\prime}$ , such that $\mathsf{N}\cup\mathsf{Q}=\mathsf{M}(T^{\prime})\setminus\{T^{\prime}\}$ . We then partition each of them into smaller subsets that are suitable for our needs.

Definition 4 (Partition of new maximal repeats).

Let $\mathsf{N}=(\mathsf{M}(T^{\prime})\setminus\mathsf{M}(T))\setminus\{T^{\prime}\}$ denote the set of new maximal repeats in $T^{\prime}$ . We divide $\mathsf{N}$ into the three following disjoint subsets $\mathsf{N}_{\mathrm{1}}=\mathsf{N}\cap\mathsf{RightM}(T)$ , $\mathsf{N}_{\mathrm{2}}=\mathsf{N}\cap\mathsf{LeftM}(T)$ , and $\mathsf{N}_{\mathrm{3}}=\mathsf{N}\setminus(\mathsf{N}_{\mathrm{1}}\cup\mathsf% {N}_{\mathrm{2}})$ . Further, we divide $\mathsf{N}_{\mathrm{3}}$ into two disjoint subsets $\mathsf{N}_{\mathrm{3B}}$ and $\mathsf{N}_{\mathrm{3A}}$ as follows: $\mathsf{N}_{\mathrm{3B}}$ is the set of strings $x\in\mathsf{N}_{\mathrm{3}}$ such that (1) $x$ is of Type $\rm{(v)}$ , and (2) there is no other right-extension of $x$ in $T^{\prime}$ than the right-extension(s) of the crossing occurrence(s) of $x$ , and $\mathsf{N}_{\mathrm{3A}}=\mathsf{N}_{\mathrm{3}}\setminus\mathsf{N}_{\mathrm{3% B}}$ .

We note that the following properties hold for $\mathsf{N}_{\mathrm{1}},\mathsf{N}_{\mathrm{2}}$ and $\mathsf{N}_{\mathrm{3}}$ by definition:

$\blacksquare$

$x\in\mathsf{N}_{\mathrm{1}}\Rightarrow x\notin\mathsf{LeftM}(T)$ because $x\notin\mathsf{M}(T)$ .
$\blacksquare$

$x\in\mathsf{N}_{\mathrm{2}}\Rightarrow x\notin\mathsf{RightM}(T)$ because $x\notin\mathsf{M}(T)$ .
$\blacksquare$

$x\in\mathsf{N}_{\mathrm{3}}\Rightarrow x\notin\mathsf{RightM}(T)\land x\notin% \mathsf{LeftM}(T)$ .

Definition 5.

Let $\mathsf{Q}=(\mathsf{M}(T^{\prime})\cap\mathsf{M}(T))\setminus\{T^{\prime}\}$ denote the set of existing maximal repeats in $T^{\prime}$ . We divide $\mathsf{Q}$ into the two following subsets $\mathsf{Q}_{\mathrm{1}}=\{x\in\mathsf{Q}\mid\mathsf{d}_{T^{\prime}}(x)>\mathsf% {d}_{T}(x)\}$ and $\mathsf{Q}_{\mathrm{2}}=\{x\in\mathsf{Q}\mid\mathsf{d}_{T^{\prime}}(x)\leq% \mathsf{d}_{T}(x)\}$ .

Namely, $\mathsf{Q}_{\mathrm{1}}$ (resp. $\mathsf{Q}_{\mathrm{2}}$ ) is the set of existing nodes of the CDAWG for which the number of out-edges increases (resp. does not increase).

Example 6.

Consider the string $T=\mathrm{cabcabcdabca}\mathbf{d}\mathrm{bcabcdabcabdcabcabcabdabcab}$ and
the string $T^{\prime}=\mathrm{cabcabcdabca|bcabcdabcabdcabcabcabdabcab}$ obtained by deleting the character $T[13]=\mathbf{d}$ from $T$ highlighted in bold. The edited position in $T^{\prime}$ is designated by a $|$ . For instance, $\mathrm{dabcab}\in\mathsf{Q}_{\mathrm{1}},\mathrm{bcabc}\in\mathsf{Q}_{\mathrm% {2}},\mathrm{abcabc}\in\mathsf{N}_{\mathrm{1}},\mathrm{abcabcab}\in\mathsf{N}_% {\mathrm{3A}},\mathrm{cabcabcdabcab}\in\mathsf{N}_{\mathrm{3B}}$ (also see Figure 4).

Figure 4: Illustration for

T^{\prime}=\mathrm{cabcabcdabca|bcabcdabcabdcabcabcabdabcab}

in Example 6 and the occurrences of

\mathrm{abcabc}\in\mathsf{N}_{\mathrm{1}}

and

\mathrm{cabcabcdabcab}\in\mathsf{N}_{\mathrm{3B}}

in

T^{\prime}

. The

|

symbol in

T^{\prime}

exhibits the edit position. The solid line boxes exhibit the crossing occurrences of

\mathrm{abcabc}

and

\mathrm{cabcabcdabcab}

in

T^{\prime}

, and the dashed line boxes exhibit the non-crossing occurrences of them in

T^{\prime}

.

Recall that $\mathsf{e}=\sum_{x\in\mathsf{M}(T)}\mathsf{d}_{T}(x)$ denotes the number of edges in $\mathsf{CDAWG}(T)$ before the edit. In the subsequent sections, we work on the three disjoint subsets $\mathsf{N}_{\mathrm{1}}\cup\mathsf{N}_{\mathrm{3A}}$ , $\mathsf{N}_{\mathrm{2}}\cup\mathsf{Q}$ , and $\mathsf{N}_{\mathrm{3B}}$ of $\mathsf{M}(T^{\prime})$ , and show that $\sum_{x\in\mathsf{N}_{\mathrm{1}}\cup\mathsf{N}_{\mathrm{3A}}}\mathsf{d}_{T^{% \prime}}(x)\leq 3\mathsf{e}+2$ (Section 4), $\sum_{x\in\mathsf{N}_{\mathrm{2}}\cup\mathsf{Q}}\mathsf{d}_{T^{\prime}}(x)\leq 3% \mathsf{e}+2$ (Section 5), and $\sum_{x\in\mathsf{N}_{\mathrm{3B}}}\mathsf{d}_{T^{\prime}}(x)\leq 2\mathsf{e}$ (Section 6). All these immediately lead to Theorem 1 that upper bounds the number of edges in $\mathsf{CDAWG}(T^{\prime})$ after the edit to $8\mathsf{e}+4$ .

The tighter upper bound $5\mathsf{e}+4$ for strings ending with $\$$ is shown in Section 7.

4 Upper bound for total out-degrees of nodes w.r.t. $\mathsf{N}_{\mathrm{1}}\cup\mathsf{N}_{\mathrm{3A}}$

In this section, we show an upper bound for the total out-degrees of the nodes corresponding to strings in $\mathsf{N}_{\mathrm{1}}\cup\mathsf{N}_{\mathrm{3A}}\subseteq\mathsf{M}(T^{% \prime})$ . Recall that $x\in\mathsf{N}_{\mathrm{1}}\cup\mathsf{N}_{\mathrm{3A}}$ implies $x\notin\mathsf{LeftM}(T)$ .

We first describe useful properties of strings $x\in\mathsf{N}_{\mathrm{1}}\cup\mathsf{N}_{\mathrm{3A}}$ .

Lemma 7.

Any $x\in\mathsf{N}_{\mathrm{1}}\cup\mathsf{N}_{\mathrm{3A}}$ occurs in $T$ .

Proof.

In the case $x\in\mathsf{N}_{\mathrm{1}}$ , since $x\in\mathsf{RightM}(T)$ , $x$ occurs in $T$ .

Let us consider the case $x\in\mathsf{N}_{\mathrm{3A}}$ that is of Type $\rm{(i)}$ , $\rm{(ii)}$ , $\rm{(iii)}$ or $\rm{(iv)}$ . Since $x$ is not of Type $\rm{(v)}$ , if all occurrences of $x$ in $T^{\prime}$ are crossing occurrences of $x$ in $T^{\prime}$ , then $x\notin\mathsf{M}(T^{\prime})$ . Therefore, $x$ occurs in $T$ .

Let us consider the case $x\in\mathsf{N}_{\mathrm{3A}}$ that is of Type $\rm{(v)}$ . Due to the definition of $\mathsf{N}_{\mathrm{3A}}$ , there exists a distinct right-extension of $x$ in $T^{\prime}$ other than the right-extension(s) of the crossing occurrence(s) of $x$ . Therefore, there is a non-crossing occurrence of $x$ in $T^{\prime}$ , which implies that $x$ occurs in $T$ (see also Figure 5). $\hfill\blacktriangleleft$

Figure 5: Illustration for Lemma 7 where

i

is the edited position and

a, b, c

differ from each other.

Lemma 8.

For any $x\in\mathsf{N}_{\mathrm{1}}\cup\mathsf{N}_{\mathrm{3A}}$ that is of Type $\rm{(i)}$ , $\rm{(ii)}$ or $\rm{(iii)}$ , there does not exist $y\in\mathsf{N}_{\mathrm{1}}\cup\mathsf{N}_{\mathrm{3A}}$ such that $|y|>|x|$ and $S_{x_{L}}=S_{{y}_{G}}$ , where $G\in\{L,R\}$ .

Proof.

If $x_{L}$ is a prefix of $T^{\prime}$ , then clearly there is no $y$ satisfying $|y|>|x|$ and $S_{x_{L}}=S_{{y}_{G}}$ . In what follows, we consider the case that $x_{L}$ is not a prefix of $T^{\prime}$ .

For a contrary, suppose that for $x\in\mathsf{N}_{\mathrm{1}}\cup\mathsf{N}_{\mathrm{3A}}$ that is of Type $\rm{(i)}$ , $\rm{(ii)}$ or $\rm{(iii)}$ , there exists $y\in\mathsf{N}_{\mathrm{1}}\cup\mathsf{N}_{\mathrm{3A}}$ such that $|y|>|x|$ and $S_{x_{L}}=S_{{y}_{G}}$ , where $G\in\{L,R\}$ . See also Figure 6. Let $a$ be the character immediately before $x_{L}$ . Since $x$ is of Type $\rm{(i)}$ , $\rm{(ii)}$ or $\rm{(iii)}$ , every crossing occurrence of $x$ in $T^{\prime}$ is immediately preceded by $a$ . Because $x\in\mathsf{M}(T^{\prime})$ , it holds that $x\in\mathsf{Prefix}(T^{\prime})$ , or there is a distinct character $b\in\Sigma\setminus\{a\}$ such that $b x$ occurs in $T^{\prime}$ . This implies that there is a non-crossing occurrence of $x$ in $T^{\prime}$ , which is as a prefix of $T$ or is immediately preceded by $b$ in $T$ . By Lemma 7, $y$ occurs in $T$ , and thus $a x$ that is a suffix of $y$ also occurs in $T$ . Hence $x\in\mathsf{LeftM}(T)$ , however, this contradicts that $x\notin\mathsf{LeftM}(T)$ . $\hfill\blacktriangleleft$

Figure 6: Illustration for Lemma 8: impossible occurrences of

x

and

y

with

S_{x_{L}}=S_{y_{G}}

.

Lemma 9.

For any $x\in\mathsf{N}_{\mathrm{1}}\cup\mathsf{N}_{\mathrm{3A}}$ that is of Type $\rm{(iv)}$ or $\rm{(v)}$ , there do not exist $y,z\in\mathsf{N}_{\mathrm{1}}\cup\mathsf{N}_{\mathrm{3A}}$ with $|y|>|x|$ and $|z|>|x|$ satisfying $S_{x_{L}}=S_{{y}_{G}}$ and $S_{x_{R}}=S_{{z}_{F}}$ simultaneously, where $G,F\in\{L,R\}$ .

Proof.

If $x_{L}$ is a prefix of $T^{\prime}$ , then clearly there is no $y$ satisfying $|y|>|x|$ and $S_{x_{L}}=S_{{y}_{G}}$ . In what follows, we consider the case that $x_{L}$ is not a prefix of $T^{\prime}$ .

For a contrary, suppose that for $x\in\mathsf{N}_{\mathrm{1}}\cup\mathsf{N}_{\mathrm{3A}}$ that is of Type $\rm{(iv)}$ or $\rm{(v)}$ , there exist $y,z\in\mathsf{N}_{\mathrm{1}}\cup\mathsf{N}_{\mathrm{3A}}$ with $|y|>|x|$ and $|z|>|x|$ such that $S_{x_{L}}=S_{{y}_{G}}$ and $S_{x_{R}}=S_{{z}_{F}}$ at the same time, where $G,F\in\{L,R\}$ . Let the character immediately before $x_{L}$ and the character immediately before $x_{R}$ be $a$ and $c$ ( $a\neq c$ ), respectively. By Lemma 7, $y$ and $z$ occur in $T$ , and thus $a x$ that is a suffix of $y$ and $c x$ that is a suffix of $z$ both occur in $T$ . Therefore, $x\in\mathsf{LeftM}(T)$ , however, this contradicts that $x\notin\mathsf{LeftM}(T)$ . $\hfill\blacktriangleleft$

4.1 Correspondence between $\mathsf{N}_{\mathrm{1}}\cup\mathsf{N}_{\mathrm{3A}}$ and $\mathsf{M}(T)$

For any $x\in\mathsf{N}_{\mathrm{1}}\cup\mathsf{N}_{\mathrm{3A}}$ that is of Type $\rm{(i)}$ , $\rm{(ii)}$ or $\rm{(iii)}$ , we associate $x$ with $S_{x_{L}}$ . For any $x\in\mathsf{N}_{\mathrm{1}}\cup\mathsf{N}_{\mathrm{3A}}$ that is of Type $\rm{(iv)}$ or $\rm{(v)}$ , if there does not exist $y\in\mathsf{N}_{\mathrm{1}}\cup\mathsf{N}_{\mathrm{3A}}$ such that $|y|>|x|$ and $S_{x_{L}}=S_{{y}_{G}}$ with $G\in\{L,R\}$ , we associate $x$ with $S_{x_{L}}$ , and otherwise we associate $x$ with $S_{x_{R}}$ .

By Lemma 8 and Lemma 9, each $x\in\mathsf{N}_{\mathrm{1}}\cup\mathsf{N}_{\mathrm{3A}}$ can be associated to a distinct string $S_{x_{G}}$ with $G\in\{L,R\}$ . Note however that $S_{x_{G}}$ may not be maximal in $T$ . Thus we introduce a function $U$ that bridges each $x\in\mathsf{N}_{\mathrm{1}}\cup\mathsf{N}_{\mathrm{3A}}$ to a distinct maximal substring in $T$ .

Definition 10.

For any $x\in\mathsf{N}_{\mathrm{1}}\cup\mathsf{N}_{\mathrm{3A}}$ , let $U(x)=\mathsf{lexp}_{T}({S_{x_{G}}})$ (see Figure 7).

By Lemma 7, $x$ occurs in $T$ and thus its suffix $S_{x_{G}}$ also occurs in $T$ . Hence $U(x)=\mathsf{lexp}_{T}({S_{x_{G}}})$ is well defined.

Figure 7: Illustration for

U(x)

(a\neq b)

.

Lemma 11.

For any $x\in\mathsf{N}_{\mathrm{1}}\cup\mathsf{N}_{\mathrm{3A}}$ , $U(x)\in\mathsf{M}(T)$ .

Proof.

By Definition 10, $U(x)=\mathsf{lexp}_{T}({S_{x_{G}}})\in\mathsf{LeftM}(T)$ . Therefore, it suffices for us to prove $U(x)\in\mathsf{RightM}(T)$ . From now on, we consider the four following cases:

Case (a) $x\in\mathsf{N}_{\mathrm{1}}$ .

In this case, $x\in\mathsf{RightM}(T)$ , therefore $S_{x_{G}}$ that is a suffix of $x$ also satisfies $S_{x_{G}}\in\mathsf{RightM}(T)$ . Hence, $U(x)=\mathsf{lexp}_{T}({S_{x_{G}}})\in\mathsf{RightM}(T)$ .

Case (b) $x\in\mathsf{N}_{\mathrm{3A}}$ and $𝒙$ is of Type $\rm{(i)}$ , $\rm{(ii)}$ or $\rm{(iv)}$ .

Let the character immediately after all crossing occurrences of $x$ in $T^{\prime}$ be $a$ . There exists $xb\>(b\neq a)$ in $T^{\prime}$ or $x\in\mathsf{Suffix}(T^{\prime})$ because $x\in\mathsf{M}(T^{\prime})$ . Since the character immediately after all crossing occurrences of $x$ in $T^{\prime}$ is $a$ , then there exists $xb\>(b\neq a)$ or $x\in\mathsf{Suffix}(T)$ in $T$ . Hence, $S_{x_{G}}\in\mathsf{RightM}(T)$ since the character immediately after $S_{x_{G}}$ is $a$ . Thus, $U(x)=\mathsf{lexp}_{T}({S_{x_{G}}})\in\mathsf{RightM}(T)$ .

Case (c) $x\in\mathsf{N}_{\mathrm{3A}}$ and $𝒙$ is of Type $\rm{(iii)}$ .

Since $x$ is of Type $\rm{(iii)}$ , we associate $x$ with $S_{x_{L}}$ . Because $x$ is of Type $\rm{(iii)}$ and $S_{x_{L}}$ is a suffix of a $S_{x_{R}}$ , $S_{x_{G}}\in\mathsf{RightM}(T)$ holds. Thus, $U(x)=\mathsf{lexp}_{T}({S_{x_{G}}})\in\mathsf{RightM}(T)$ .

Case (d) $x\in\mathsf{N}_{\mathrm{3A}}$ and $𝒙$ is of Type $\rm{(v)}$ .

Let the character immediately after $S_{x_{G}}$ be $a$ . Since there exists a distinct right-extension of $x$ in $T^{\prime}$ other than the right-extension(s) of the crossing occurrence(s) of $x$ , there exists $x b$ $(b\neq a)$ in $T$ . Therefore, $S_{x_{G}}\in\mathsf{RightM}(T)$ . Thus, $U(x)=\mathsf{lexp}_{T}({S_{x_{G}}})\in\mathsf{RightM}(T)$ .

Consequently, we have $U(x)\in\mathsf{M}(T)$ . $\hfill\blacktriangleleft$

The next lemma states the uniqueness of $U(x)$ .

Lemma 12.

For any $x,y\in\mathsf{N}_{\mathrm{1}}\cup\mathsf{N}_{\mathrm{3A}}$ with $x\neq y$ , $U(x)\neq U(y)$ .

Proof.

Suppose that there exist $x,y\in\mathsf{N}_{\mathrm{1}}\cup\mathsf{N}_{\mathrm{3A}}$ such that $x\neq y$ and $U(x)=U(y)$ . Let $x$ and $y$ correspond to $S_{x_{G}}$ and $S_{y_{F}}$ , respectively, where $G,F\in\{L,R\}$ . Let $U(x)=AS_{x_{G}},U(y)=BS_{y_{F}}\>(A,B\in\mathsf{Substr}(T))$ , and assume without loss of generality that $|S_{x_{G}}|<|S_{y_{F}}|$ due to Lemma 8 and Lemma 9. Then $|A|>|B|$ because $U(x)=U(y)$ . Since $U(y)=BS_{y_{F}}\in\mathsf{M}(T)$ by Lemma 11, and since $BS_{x_{G}}$ is a prefix of $BS_{y_{F}}$ (see Figure 8), we have $BS_{x_{G}}\in\mathsf{LeftM}(T)$ . This contradicts $\mathsf{lexp}_{T}({S_{x_{G}}})=AS_{x_{G}}$ . $\hfill\blacktriangleleft$

Figure 8: Illustration for the proof of Lemma 12, where

U(x)=U(y)

.

4.2 Upper bound w.r.t. $\mathsf{N}_{\mathrm{1}}\cup\mathsf{N}_{\mathrm{3A}}$

Lemma 13.

$\sum_{x\in\mathsf{N}_{\mathrm{1}}\cup\mathsf{N}_{\mathrm{3A}}}\mathsf{d}_{T^{% \prime}}(x)\leq 3\mathsf{e}+2$ .

Proof.

Let $U(x)=\mathsf{lexp}_{T}({S_{x_{G}}})$ , where $G\in\{L,R\}$ . Since $S_{x_{G}}$ is a suffix of $x$ , $\mathsf{d}_{T}(x)\leq\mathsf{d}_{T}(U(x))$ . Since there are at most two distinct characters immediately after the crossing occurrences of $x$ , $\mathsf{d}_{T^{\prime}}(x)\leq\mathsf{d}_{T}(U(x))+2$ . For $U(x)\neq T$ , we have $\mathsf{d}_{T}(U(x))\geq 1$ . Thus $\mathsf{d}_{T^{\prime}}(x)\leq\mathsf{d}_{T}(U(x))+2\leq 3\mathsf{d}_{T}(U(x))$ . For $U(x)=T$ , we have $\mathsf{d}_{T}(U(x))=0$ . Thus $\mathsf{d}_{T^{\prime}}(x)\leq 2$ . By using Lemma 12 and summing up these, we get $\sum_{x\in\mathsf{N}_{\mathrm{1}}\cup\mathsf{N}_{\mathrm{3A}}}\mathsf{d}_{T^{% \prime}}(x)\leq{\sum_{x\in\mathsf{N}_{\mathrm{1}}\cup\mathsf{N}_{\mathrm{3A}}}% 3\mathsf{d}_{T}(U(x))}+2\leq 3\mathsf{e}+2$ . $\hfill\blacktriangleleft$

5 Upper bound for total out-degrees of nodes w.r.t. $\mathsf{N}_{\mathrm{2}}\cup\mathsf{Q}$

In this section, we show an upper bound for the total out-degrees of nodes corresponding to strings that are elements of $\mathsf{N}_{\mathrm{2}}\cup\mathsf{Q}\subseteq\mathsf{M}(T^{\prime})$ .

We first present properties of the strings in $\mathsf{N}_{\mathrm{2}}\cup\mathsf{Q}$ . In particular, we focus on the strings in $\mathsf{N}_{\mathrm{2}}\cup\mathsf{Q}_{\mathrm{1}}$ , as the strings in $\mathsf{Q}_{\mathrm{2}}$ are less important and can be handled in a trivial manner.

Lemma 14.

Any $x\in\mathsf{N}_{\mathrm{2}}\cup\mathsf{Q}_{\mathrm{1}}$ occurs in $T$ .

Proof.

Since $x\in\mathsf{N}_{\mathrm{2}}\cup\mathsf{Q}_{\mathrm{1}}$ , $x\in\mathsf{LeftM}(T)$ . Thus $x\in\mathsf{N}_{\mathrm{2}}\cup\mathsf{Q}_{\mathrm{1}}$ occurs in $T$ . $\hfill\blacktriangleleft$

Lemma 15.

For any $x\in\mathsf{N}_{\mathrm{2}}\cup\mathsf{Q}_{\mathrm{1}}$ that is of Type $\rm{(i)}$ , $\rm{(ii)}$ or $\rm{(iv)}$ , there does not exist $y\in\mathsf{N}_{\mathrm{2}}\cup\mathsf{Q}_{\mathrm{1}}$ such that $|y|>|x|$ and $P_{x_{G}}=P_{y_{F}}$ , where $G,F\in\{L,R\}$ .

Proof.

The case that $x\in\mathsf{N}_{\mathrm{2}}$ follows from a symmetrical argument to Lemma 8, in which $y$ may belong to $\mathsf{N}_{\mathrm{2}}$ or $\mathsf{Q}_{\mathrm{1}}$ . Let us consider the case that $x\in\mathsf{Q}_{\mathrm{1}}$ . Suppose that for $x\in\mathsf{Q}_{\mathrm{1}}$ which is of Type $\rm{(i)}$ , $\rm{(ii)}$ or $\rm{(iv)}$ , there is $y\in\mathsf{N}_{\mathrm{2}}\cup\mathsf{Q}_{\mathrm{1}}$ such that $|y|>|x|$ and $P_{x_{G}}=P_{y_{F}}$ , where $G,F\in\{L,R\}$ . If $x_{R}$ is a suffix of $T^{\prime}$ , then there is no $y$ such that $|y|>|x|$ and $P_{x_{G}}=P_{y_{F}}$ . From now on consider the case that $x_{R}$ is not a suffix of $T^{\prime}$ . Let $b$ be the character immediately after $x_{G}$ . Then, since $x$ is of Type $\rm{(i)}$ , $\rm{(ii)}$ or $\rm{(iv)}$ , character $b$ immediately follows every crossing occurrence of $x$ in $T^{\prime}$ . Note that $x b$ is a prefix of $y$ . Due to Lemma 14, $y$ occurs in $T$ , implying $x b$ also occurs in $T$ . Thus the number of right-extensions of $x$ in $T^{\prime}$ is no more than the number of right-extensions of $x$ in $T$ . However, this contradicts $x\in\mathsf{Q}_{\mathrm{1}}$ . $\hfill\blacktriangleleft$

Lemma 16.

For any $x\in\mathsf{N}_{\mathrm{2}}\cup\mathsf{Q}_{\mathrm{1}}$ that is of Type $\rm{(iii)}$ or $\rm{(v)}$ , there do not exist $y,z\in\mathsf{N}_{\mathrm{2}}\cup\mathsf{Q}_{\mathrm{1}}$ with $|y|>|x|$ and $|z|>|x|$ satisfying $P_{x_{L}}=P_{{y}_{G}}$ and $P_{x_{R}}=P_{{z}_{F}}$ simultaneously, where $G,F\in\{L,R\}$ .

Proof.

If $x_{R}$ is a suffix of $T^{\prime}$ , then clearly there is no $z$ satisfying $|z|>|x|$ and $P_{x_{R}}=S_{{z}_{G}}$ . In what follows, we consider the case that $x_{R}$ is not a suffix of $T^{\prime}$ .

Suppose that for $x\in\mathsf{N}_{\mathrm{2}}\cup\mathsf{Q}_{\mathrm{1}}$ which is of Type $\rm{(iii)}$ or $\rm{(v)}$ , there exist $y,z\in\mathsf{N}_{\mathrm{2}}\cup\mathsf{Q}_{\mathrm{1}}$ with $|y|>|x|$ , $|z|>|x|$ that satisfy $P_{x_{L}}=P_{{y}_{G}}$ and $P_{x_{R}}=P_{{z}_{F}}$ at the same time, where $G,F\in\{L,R\}$ . Let $b$ and $d$ ( $b\neq d$ ) be the character immediately after $x_{L}$ in $T^{\prime}$ and the character immediately after $x_{R}$ in $T^{\prime}$ , respectively. By Lemma 14, $y$ and $z$ occur in $T$ , and hence $x b$ that is a prefix of $y$ and $x d$ that is a prefix of $z$ also occur in $T$ . Therefore, $x\in\mathsf{RightM}(T)$ . However, if $x\in\mathsf{N}_{\mathrm{2}}(T)$ , this contradicts $x\notin\mathsf{RightM}(T)$ . Also, if $x\in\mathsf{Q}_{\mathrm{1}}$ , the number of right-extensions of $x$ in $T^{\prime}$ does not increase from the number of right-extensions of $x$ in $T$ . However, this contradicts $x\in\mathsf{Q}_{\mathrm{1}}$ . $\hfill\blacktriangleleft$

5.1 Correspondence between $\mathsf{N}_{\mathrm{2}}\cup\mathsf{Q}_{\mathrm{1}}$ and $\mathsf{M}(T)$

For any $x\in\mathsf{N}_{\mathrm{2}}\cup\mathsf{Q}_{\mathrm{1}}$ that is of Type $\rm{(i)}$ , $\rm{(ii)}$ or $\rm{(iv)}$ , then we associate $x$ with both $P_{x_{L}}$ and $P_{x_{R}}$ . For any $x\in\mathsf{N}_{\mathrm{2}}\cup\mathsf{Q}_{\mathrm{1}}$ that is of Type $\rm{(iii)}$ or $\rm{(v)}$ ,

$\blacksquare$

if there exists $y\in\mathsf{N}_{\mathrm{2}}\cup\mathsf{Q}_{\mathrm{1}}$ with $|y|>|x|$ such that $P_{x_{R}}=P_{{y}_{G}}$ where $G\in\{L,R\}$ , then we associate $x$ with $P_{x_{L}}$ (see Figure 9);
$\blacksquare$

if there exists $y\in\mathsf{N}_{\mathrm{2}}\cup\mathsf{Q}_{\mathrm{1}}$ with $|y|>|x|$ such that $P_{x_{L}}=P_{{y}_{G}}$ where $G\in\{L,R\}$ , then we associate $x$ with $P_{x_{R}}$ (see Figure 10);
$\blacksquare$

otherwise, we associate $x$ with both $P_{x_{L}}$ and $P_{x_{R}}$ .

Figure 9: When there exists

y\in\mathsf{N}_{\mathrm{2}}\cup\mathsf{Q}_{\mathrm{1}}

with

|y|>|x|

such that

P_{x_{R}}=P_{{y}_{G}}

, where

G\in\{L,R\}

.

Figure 10: When there exists

y\in\mathsf{N}_{\mathrm{2}}\cup\mathsf{Q}_{\mathrm{1}}

with

|y|>|x|

such that

P_{x_{L}}=P_{{y}_{G}}

, where

G\in\{L,R\}

.

By Lemmas 15 and 16, each $x\in\mathsf{N}_{\mathrm{2}}\cup\mathsf{Q}_{\mathrm{1}}$ corresponds to a distinct string $P_{x_{G}}$ , where $G\in\{L,R\}$ . Below, for each $x\in\mathsf{N}_{\mathrm{2}}\cup\mathsf{Q}_{\mathrm{1}}$ , we define $H(x)$ and $I(x)$ to which $x$ corresponds:

Definition 17.

For each $x\in\mathsf{N}_{\mathrm{2}}\cup\mathsf{Q}_{\mathrm{1}}$ associated to ${P_{x_{L}}}$ , let $H(x)=\mathsf{rexp}_{T}({P_{x_{L}}})$ . For each $x\in\mathsf{N}_{\mathrm{2}}\cup\mathsf{Q}_{\mathrm{1}}$ associated to ${P_{x_{R}}}$ , let $I(x)=\mathsf{rexp}_{T}({P_{x_{R}}})$ . See Figure 11. When there is only one crossing occurrence of $x$ (i.e. $x_{L}=x_{R}$ ), only $H(x)$ is defined as above and $I(x)$ is undefined.

$H(x)$ (resp. $I(x)$ ) is undefined for any $x\in\mathsf{N}_{\mathrm{2}}\cup\mathsf{Q}_{\mathrm{1}}$ that is not associated to ${P_{x_{L}}}$ (resp. ${P_{x_{R}}}$ ).

By Lemma 14 every $x\in\mathsf{N}_{\mathrm{2}}\cup\mathsf{Q}_{\mathrm{1}}$ occurs in $T$ , and thus $H(x)$ and $I(x)$ are well defined when $x$ is associated to $P_{x_{L}}$ and $P_{x_{R}}$ , respectively.

Figure 11: Illustration for

H(x)

and

I(x)

(

a\neq b,c\neq d

).

Lemma 18.

For any $x\in\mathsf{N}_{\mathrm{2}}\cup\mathsf{Q}_{\mathrm{1}}$ , $H(x)\in\mathsf{M}(T)$ if $H(x)$ is defined, and $I(x)\in\mathsf{M}(T)$ if $I(x)$ is defined.

Proof.

By Definition 17, $H(x),I(x)\in\mathsf{RightM}(T)$ . Therefore, it suffices for us to prove $H(x),I(x)\in\mathsf{LeftM}(T)$ . For any $x\in\mathsf{N}_{\mathrm{2}}\cup\mathsf{Q}_{\mathrm{1}}$ , $x\in\mathsf{LeftM}(T)$ . Since $P_{x_{G}}\>(G\in\{L,R\})$ is a prefix of $x$ , we have $P_{x_{G}}\in\mathsf{LeftM}(T)$ . Hence $H(x),I(x)\in\mathsf{LeftM}(T)$ holds. $\hfill\blacktriangleleft$

Lemma 19.

For any $x,y\in\mathsf{N}_{\mathrm{1}}\cup\mathsf{Q}_{\mathrm{1}}$ with $x\neq y$ , let $\mathcal{L}$ be a list of $H(x)$ , $I(x)$ , $H(y)$ , $I(y)$ which are defined. Then the elements in $\mathcal{L}$ differ from each other.

Proof.

By a symmetrical argument to Lemma 12. $\hfill\blacktriangleleft$

5.2 Upper bound w.r.t. $\mathsf{N}_{\mathrm{2}}\cup\mathsf{Q}$

Lemma 20.

$\sum_{x\in\mathsf{N}_{\mathrm{2}}\cup\mathsf{Q}}\mathsf{d}_{T^{\prime}}(x)\leq 3% \mathsf{e}+2$ .

Proof.

Below, we consider all the four possible cases depending on whether $x\in\mathsf{N}_{\mathrm{2}}$ or $x\in\mathsf{Q}_{\mathrm{1}}$ , and whether $H(x),I(x)\neq T$ .

When $x\in\mathsf{N}_{\mathrm{2}}$ and $H(x),I(x)\neq T$ .

$\blacksquare$

First, we consider the case that $x$ is associated with both $H(x)$ and $I(x)$ . Since $x\in\mathsf{N}_{\mathrm{2}}$ , then $x\notin\mathsf{RightM}(T)$ . Therefore, the number of characters that are immediately after $x$ in $T$ is at most one. Moreover, there are at most two distinct characters immediately after the crossing occurrences of $x$ . Hence, there are at most three distinct characters immediately after $x$ in $T^{\prime}$ , namely we have

$\mathsf{d}_{T^{\prime}}(x)\leq 3.$ (1)

In addition, since ${H(x),I(x)\neq T}$ , it holds that $\mathsf{d}_{T}(H(x)),\mathsf{d}_{T}(I(x))\geq 1$ . By Inequality 1, we get $\mathsf{d}_{T^{\prime}}(x)\leq 3\leq\mathsf{d}_{T}(H(x))+\mathsf{d}_{T}(I(x))+% 1\leq 2\mathsf{d}_{T}(H(x))+2\mathsf{d}_{T}(I(x)).$
$\blacksquare$
Second, we consider the case that $x$ is associated with only one of $H(x)$ or $I(x)$ .
- –
  
  Assume that we associate $x$ with $H(x)$ . Since $x\in\mathsf{N}_{\mathrm{2}}$ , then $x\notin\mathsf{RightM}(T)$ . Therefore, the number of characters immediately after $x$ in $T$ is at most one. In this case, we do not associate $x$ with $I(x)$ , hence, $x$ has only one crossing occurrence or there exists $y\in\mathsf{N}_{\mathrm{2}}\cup\mathsf{Q}_{\mathrm{1}}$ such that $|y|>|x|$ and $P_{x_{R}}=P_{{y}_{G}}$ where $G\in\{L,R\}$ . When $x$ has only one crossing occurrence, there are at most one character immediately after the crossing occurrence of $x$ . When there exists $y\in\mathsf{N}_{\mathrm{2}}\cup\mathsf{Q}_{\mathrm{1}}$ such that $|y|>|x|$ and $P_{x_{R}}=P_{{y}_{G}}$ where $G\in\{L,R\}$ , then such $y$ occurs in $T$ due to Lemma 14. Therefore, although there are at most two distinct characters immediately after the crossing occurrences of $x$ , one of them is the character immediately after $x$ in $T$ as shown in Figure 12. Hence, we have
  
  $\mathsf{d}_{T^{\prime}}(x)\leq 2.$ (2)
  
  In addition, since ${H(x)\neq T}$ , then $\mathsf{d}_{T}(H(x))\geq 1$ holds. By Inequality 2, we get $\mathsf{d}_{T^{\prime}}(x)\leq 2\leq\mathsf{d}_{T}(H(x))+1\leq 2\mathsf{d}_{T}% (H(x)).$
- –
  
  Let us assume that we associate $x$ with $I(x)$ . In the same way as we associate $x$ with $H(x)$ , we get $\mathsf{d}_{T^{\prime}}(x)\leq 2\leq\mathsf{d}_{T}(I(x))+1\leq 2\mathsf{d}_{T}% (I(x))$ .

Figure 12:

x a

occurs in

T

, where

a

is the character immediately after the crossing occurrence

x_{R}

.

When $x\in\mathsf{N}_{\mathrm{2}}$ and $H(x)=T$ or $I(x)=T$ .

$\blacksquare$
Let $H(x)=T$ . Now that $H(x)$ is defined, $x$ is associated with $H(x)$ .
- –
  
  First, we consider the case that we associate $x$ with both $H(x)$ and $I(x)$ . In the same way as in Inequality 1, we get $\mathsf{d}_{T^{\prime}}(x)\leq 3$ . In addition, since $H(x)=T$ and Lemma 19 holds, $I(x)\neq T$ and thus $\mathsf{d}_{T}(I(x))\geq 1$ holds. Hence, we have $\mathsf{d}_{T^{\prime}}(x)\leq 3\leq\mathsf{d}_{T}(I(x))+2\leq 2\mathsf{d}_{T}% (H(x))+2\mathsf{d}_{T}(I(x))+2$ .
- –
  
  Second, we consider the case that we only associate $x$ with $H(x)$ . Since $H(x)=T$ , $\mathsf{d}_{T}(H(x))=0$ holds. In the same way as in Inequality 2, we get $\mathsf{d}_{T^{\prime}}(x)\leq 2$ . Thus, we have $\mathsf{d}_{T^{\prime}}(x)\leq 2\leq 2\mathsf{d}_{T}(H(x))+2$ .
$\blacksquare$

Let $I(x)=T$ . Now that $I(x)$ is defined, $x$ is associated with $I(x)$ . In the same way as in the case for $H(x)=T$ , we get $\mathsf{d}_{T^{\prime}}(x)\leq 3\leq\mathsf{d}_{T}(H(x))+2\leq 2\mathsf{d}_{T}% (H(x))+2\mathsf{d}_{T}(I(x))+2$ in the case that we associate $x$ with both $H(x)$ and $I(x)$ , and we get $\mathsf{d}_{T^{\prime}}(x)\leq 2\leq 2\mathsf{d}_{T}(I(x))+2$ in the case that we only associate $x$ with $I(x)$ .

When $x\in\mathsf{Q}_{\mathrm{1}}$ and $H(x),I(x)\neq T$ .

Here, we analyze $\mathsf{d}_{T^{\prime}}(x)-\mathsf{d}_{T}{(x)}$ since $x\in\mathsf{Q}_{\mathrm{1}}$ .

$\blacksquare$

First, we consider the case that we associate $x$ with both $H(x)$ and $I(x)$ . There are at most two distinct characters immediately after the crossing occurrences of $x$ . Hence,

$\mathsf{d}_{T^{\prime}}(x)-\mathsf{d}_{T}{(x)}\leq 2.$ (3)

In addition, since ${H(x),I(x)\neq T}$ , then $\mathsf{d}_{T}(H(x)),\mathsf{d}_{T}(I(x))\geq 1$ holds. By Inequality 3, we get $\mathsf{d}_{T^{\prime}}(x)-\mathsf{d}_{T}{(x)}\leq 2\leq\mathsf{d}_{T}(H(x))+% \mathsf{d}_{T}(I(x))\leq\mathsf{d}_{T}(H(x))+\mathsf{d}_{T}(I(x))$ .
$\blacksquare$

Second, we consider the case that we associate $x$ with only one of $H(x)$ or $I(x)$ . Here, let us assume that we associate $x$ with $H(x)$ . In this case, we do not associate $x$ with $I(x)$ , hence, $x$ has only one crossing occurrence or there exists $y\in\mathsf{N}_{\mathrm{2}}\cup\mathsf{Q}_{\mathrm{1}}$ such that $|y|>|x|$ and $P_{x_{R}}=P_{{y}_{G}}$ where $G\in\{L,R\}$ . When $x$ has only one crossing occurrence, there are at most one character immediately after the crossing occurrence of $x$ . When there exists $y\in\mathsf{N}_{\mathrm{2}}\cup\mathsf{Q}_{\mathrm{1}}$ such that $|y|>|x|$ and $P_{x_{R}}=P_{{y}_{G}}$ where $G\in\{L,R\}$ , then such $y$ occurs in $T$ due to Lemma 14. Therefore, although there are at most two distinct characters immediately after the crossing occurrences of $x$ , one of them is the character immediately after $x$ in $T$ as shown in Figure 12. Hence, we have

$\mathsf{d}_{T^{\prime}}(x)-\mathsf{d}_{T}{(x)}\leq 1.$ (4)

In addition, since ${H(x)\neq T}$ , then $\mathsf{d}_{T}(H(x))\geq 1$ holds. By Inequality 4, we get $\mathsf{d}_{T^{\prime}}(x)-\mathsf{d}_{T}{(x)}\leq 1\leq\mathsf{d}_{T}(H(x))$ . In the case that we associate $x$ with $I(x)$ , in the same way as we associate $x$ with $H(x)$ , we get $\mathsf{d}_{T^{\prime}}(x)-\mathsf{d}_{T}{(x)}\leq 1\leq\mathsf{d}_{T}(I(x))$ .

When $x\in\mathsf{Q}_{\mathrm{1}}$ and $H(x)=T$ or $I(x)=T$ .

Here, we analyze $\mathsf{d}_{T^{\prime}}(x)-\mathsf{d}_{T}{(x)}$ since $x\in\mathsf{Q}_{\mathrm{1}}$ .

$\blacksquare$
Let $H(x)=T$ . Since $H(x)$ is defined, $x$ is associated with $H(x)$ .
- –
  
  First, let us consider the case that we associate $x$ with both $H(x)$ and $I(x)$ . In the same way as in Inequality 3, we get $\mathsf{d}_{T^{\prime}}(x)-\mathsf{d}_{T}{(x)}\leq 2$ . In addition, since $H(x)=T$ and Lemma 19 holds, $I(x)\neq T$ and thus $\mathsf{d}_{T}(I(x))\geq 1$ holds. Hence $\mathsf{d}_{T^{\prime}}(x)-\mathsf{d}_{T}{(x)}\leq 2\leq\mathsf{d}_{T}(I(x))+1% \leq\mathsf{d}_{T}(H(x))+\mathsf{d}_{T}(I(x))+1$ .
- –
  
  Second, let us consider the case that we only associate $x$ with $H(x)$ . Since $H(x)=T$ , $\mathsf{d}_{T}(H(x))=0$ holds. In the same way as in Inequality 4, we get $\mathsf{d}_{T^{\prime}}(x)-\mathsf{d}_{T}{(x)}\leq 1$ . Thus, we have $\mathsf{d}_{T^{\prime}}(x)-\mathsf{d}_{T}{(x)}\leq 1\leq\mathsf{d}_{T}(H(x))+1$ .
$\blacksquare$

Let $I(x)=T$ . Since $I(x)$ is defined, $x$ is associated with $I(x)$ . In the same way as in the case for $H(x)=T$ , we get $\mathsf{d}_{T^{\prime}}(x)-\mathsf{d}_{T}{(x)}\leq 2\leq\mathsf{d}_{T}(H(x))+1% \leq\mathsf{d}_{T}(H(x))+\mathsf{d}_{T}(I(x))+1$ in the case that we associate $x$ with both $H(x)$ and $I(x)$ , and we get $\mathsf{d}_{T^{\prime}}(x)-\mathsf{d}_{T}{(x)}\leq 1\leq\mathsf{d}_{T}(I(x))+1$ in the case that we only associate $x$ with $I(x)$ .

Table 1: Upper bounds for each case of Lemma 20.

	When $H(x)\neq T\land I(x)\neq T$	When $H(x)=T\lor I(x)=T$
$\mathsf{d}_{T^{\prime}}(x)-\mathsf{d}_{T}{(x)}\>(x\in\mathsf{Q}_{\mathrm{1}})$	$\leq\mathsf{d}_{T}{(H(x))}+\mathsf{d}_{T}{(I(x))}$	$\leq\mathsf{d}_{T}{(H(x))}+\mathsf{d}_{T}{(I(x))}+1$
$\mathsf{d}_{T^{\prime}}(x)\>(x\in\mathsf{N}_{\mathrm{2}})$	$\leq 2(\mathsf{d}_{T}{(H(x))}+\mathsf{d}_{T}{(I(x))})$	$\leq 2(\mathsf{d}_{T}{(H(x))}+\mathsf{d}_{T}{(I(x))})+2$

Wrapping up.

Table 1 summarizes the bounds obtained above. For simplicity, let $\mathsf{d}_{T}{(I(x))}=0$ when $I(x)$ is undefined, and let $\mathsf{d}_{T}{(H(x))}=0$ when $H(x)$ is undefined. Note that this does not affect our upper bound analysis, since no maximal repeats in $T^{\prime}$ are associated to the undefined $H(x)$ ’s and $I(x)$ ’s. By Lemma 19, there is at most one string $x$ such that $H(x)=T$ or $I(x)=T$ . Thus, by using Lemma 19 and summing up the values in Table 1, we obtain $\sum_{x\in\mathsf{N}_{\mathrm{2}}}\mathsf{d}_{T^{\prime}}(x)+\sum_{x\in\mathsf% {Q}_{\mathrm{1}}}(\mathsf{d}_{T^{\prime}}(x)-\mathsf{d}_{T}(x))\leq 2\mathsf{e% }+2$ . Also, since the number of out-edges of $x\in\mathsf{Q}_{\mathrm{2}}$ does not increase, we get $\sum_{x\in\mathsf{Q}_{\mathrm{2}}}\mathsf{d}_{T^{\prime}}(x)+\sum_{x\in\mathsf% {Q}_{\mathrm{1}}}\mathsf{d}_{T}(x)\leq\sum_{x\in\mathsf{Q}_{\mathrm{2}}}% \mathsf{d}_{T}(x)+\sum_{x\in\mathsf{Q}_{\mathrm{1}}}\mathsf{d}_{T}(x)\leq\sum_% {x\in\mathsf{Q}}\mathsf{d}_{T}(x)\leq\sum_{x\in\mathsf{M}(T)}\mathsf{d}_{T}(x)% =\mathsf{e}$ . By adding $\sum_{x\in\mathsf{N}_{\mathrm{2}}}\mathsf{d}_{T^{\prime}}(x)+\sum_{x\in\mathsf% {Q}_{\mathrm{1}}}(\mathsf{d}_{T^{\prime}}(x)-\mathsf{d}_{T}(x))\leq 2\mathsf{e% }+2$ , we get $\sum_{x\in\mathsf{N}_{\mathrm{2}}\cup\mathsf{Q}}\mathsf{d}_{T^{\prime}}(x)\leq 3% \mathsf{e}+2$ . $\hfill\blacktriangleleft$

6 Upper bound for total out-degrees of nodes w.r.t. $\mathsf{N}_{\mathrm{3B}}$

In this section, we show an upper bound for the total out-degrees of nodes corresponding to strings that are elements of $\mathsf{N}_{\mathrm{3B}}\subseteq\mathsf{M}(T^{\prime})$ . We first describe useful properties of strings $x\in\mathsf{N}_{\mathrm{3B}}$ .

Definition 21.

For any $x\in\mathsf{N}_{\mathrm{3B}}$ , let $J_{x}$ be the string that is obtained by removing $P_{x_{R}}$ and $S_{x_{L}}$ from $x$ , namely $x=P_{x_{R}}J_{x}S_{x_{L}}$ .

Note that, by the definition of Type $\rm{(v)}$ , each $x\in\mathsf{N}_{\mathrm{3B}}$ has two or more crossing occurrences in $T^{\prime}$ . Hence $J_{x}$ always exists (possibly the empty string). See Figures 13 and 14.

Figure 13: Illustration for

J_{x}

in case of insertions and substitutions.

Figure 14: Illustration for

J_{x}

in case of deletions.

Lemma 22.

For any $x,y\in\mathsf{N}_{\mathrm{3B}}$ with $x\neq y$ , $J_{x}\neq J_{y}$ .

Proof.

For a contrary, suppose that there exist $x,y\in\mathsf{N}_{\mathrm{3B}}$ such that $x\neq y$ and $J_{x}=J_{y}$ . Since $x$ is of Type $\rm{(v)}$ , the characters immediately after $x_{L}$ and $x_{R}$ are different and let $a, b$ ( $a\neq b$ ) be these characters, respectively. If $|S_{x_{L}}|<|S_{y_{L}}|$ , then both $S_{x_{L}}a$ and $S_{x_{L}}b$ must be prefixes of $S_{y_{L}}$ (see Figures 15 and 16), which contradicts that $a\neq b$ . The other case where $|S_{x_{L}}|>|S_{y_{L}}|$ also leads to a contradiction. Hence $|S_{x_{L}}|=|S_{y_{L}}|$ , which implies $S_{x_{L}}=S_{y_{L}}$ . Also, $P_{x_{R}}=P_{y_{R}}$ follows in a symmetric manner. These imply $x=y$ , which is a contradiction. $\hfill\blacktriangleleft$

Figure 15: Illustration for Lemma 22 in case of insertions and substitutions, where

J_{x}=J_{y}

.

Figure 16: Illustration for Lemma 22 in case of deletions, where

J_{x}=J_{y}

.

6.1 Correspondence between $\mathsf{N}_{\mathrm{3B}}$ and $\mathsf{M}(T)$

For any $x\in\mathsf{N}_{\mathrm{3B}}$ , we associate $x$ with $J_{x}$ . For any $x\in\mathsf{N}_{\mathrm{3B}}$ we define $K(x)$ to which $x$ corresponds, by using $J_{x}$ , as follows:

Definition 23.

For any $x\in\mathsf{N}_{\mathrm{3B}}$ , let $K(x)=\mathsf{lexp}_{T}({\mathsf{rexp}_{T}({J_{x}})})=\mathsf{rexp}_{T}({% \mathsf{lexp}_{T}({J_{x}})})$ (see also Figure 17).

We note that $K(x)$ is well defined since $J_{x}$ is a substring of $T$ .

Figure 17: Illustration for Definition 23, where

a\neq b

and

c\neq d

.

Lemma 24.

For any $x,y\in\mathsf{N}_{\mathrm{3B}}$ with $x\neq y$ , $K(x)\neq K(y)$ .

Proof.

Suppose that there exist $x,y\in\mathsf{N}_{\mathrm{3B}}$ such that $x\neq y$ and $K(x)=K(y)$ , and without loss of generality that $|J_{x}|\leq|J_{y}|$ . Then, $J_{x}$ occurs at least twice in $J_{y}$ . Therefore, $K(x)\neq K(y)$ , however, this is a contradiction. $\hfill\blacktriangleleft$

6.2 Upper bound w.r.t. $\mathsf{N}_{\mathrm{3B}}$

Lemma 25.

$\sum_{x\in\mathsf{N}_{\mathrm{3B}}}\mathsf{d}_{T^{\prime}}(x)\leq 2\mathsf{e}$ .

Proof.

By the definition of $\mathsf{N}_{\mathrm{3B}}$ , there is no other right-extension of $x$ in $T^{\prime}$ than the right-extension(s) of the crossing occurrence(s) of $x$ . Thus there are at most two distinct characters immediately after $x$ in $T^{\prime}$ . Since $K(x)$ occurs at least twice in $T$ , $\mathsf{d}_{T}(K(x))\geq 1$ . Hence, we get $\mathsf{d}_{T^{\prime}}(x)\leq 2\leq 2\mathsf{d}_{T}(K(x))$ . Therefore, we have $\sum_{x\in\mathsf{N}_{\mathrm{3B}}}\mathsf{d}_{T^{\prime}}(x)\leq 2\mathsf{e}$ by Lemma 24. $\hfill\blacktriangleleft$

7 Tighter upper bound for strings ending with $

In this section, we consider any string ending with a unique end-marker $\$$ , and present a tighter upper bound for the worst-case multiplicative sensitivity of $\mathsf{e}$ :

Lemma 26.

For any string $T$ of length $n$ ending with a unique character $\$$ , $\mathsf{MS}(\mathsf{e},n)\leq(5\mathsf{e}+4)/\mathsf{e}$ holds.

Proof.

We first examine the upper bound in Lemma 13. When $T$ ends with a unique character $\$$ , the argument of Lemma 13 can be adapted as follows. Let $x\in\mathsf{N}_{\mathrm{1}}\cup\mathsf{N}_{\mathrm{3A}}$ , and let $U(x)$ be defined in the same way as in Lemma 13. Since every maximal repeat in the CDAWG of any string ending with $\$$ has at least two outgoing edges, we have $\mathsf{d}_{T}(U(x))\geq 2$ . From the same reasoning as in Lemma 13, it follows that $\mathsf{d}_{T^{\prime}}(x)\leq\mathsf{d}_{T}(U(x))+2$ , which can be tightened to $\mathsf{d}_{T^{\prime}}(x)\leq 2\mathsf{d}_{T}(U(x))$ when $\mathsf{d}_{T}(U(x))\geq 2$ .

By Lemma 12, the mapping $x\mapsto U(x)$ is injective. Therefore,

\sum_{x\in\mathsf{N}_{\mathrm{1}}\cup\mathsf{N}_{\mathrm{3A}}}\mathsf{d}_{T^{% \prime}}(x)\leq 2\sum_{x\in\mathsf{N}_{\mathrm{1}}\cup\mathsf{N}_{\mathrm{3A}}% }\mathsf{d}_{T}(U(x))+2\leq 2\mathsf{e}+2.

By applying similar arguments to the nodes considered in Lemma 20 and Lemma 25, we obtain upper bounds of $2\mathsf{e}+2$ and $\mathsf{e}$ , respectively.

Summing up these three bounds gives us

(2\mathsf{e}+2)+(2\mathsf{e}+2)+\mathsf{e}=5\mathsf{e}+4.

Hence, the total upper bound is $5\mathsf{e}+4$ , as claimed. $\hfill\blacktriangleleft$

8 Conclusions

This paper proved that the worst-case multiplicative sensitivity of CDAWGs is asymptotically at most 8. Our analysis is built on new combinatorial properties of maximal repeats and their right-extensions, that are incidental to an edit operation on the strings. The only known lower bound for the multiplicative sensitivity of CDAWGs is asymptotically 2 [9]. It is intriguing future work to close the gap between these upper bound and lower bound.

References

[1] Tooru Akagi, Mitsuru Funakoshi, and Shunsuke Inenaga. Sensitivity of string compressors and repetitiveness measures. Information and Computation, 291:104999, 2023. doi:10.1016/J.IC.2022.104999.
[2] Pawel Baturo, Marcin Piatkowski, and Wojciech Rytter. Usefulness of directed acyclic subword graphs in problems related to Standard Sturmian Words. Int. J. Found. Comput. Sci., 20(6):1005–1023, 2009. doi:10.1142/S0129054109007017.
[3] Djamal Belazzougui and Fabio Cunial. Fast label extraction in the CDAWG. In SPIRE 2017, pages 161–175, 2017. doi:10.1007/978-3-319-67428-5_14.
[4] Anselm Blumer, J. Blumer, David Haussler, Ross McConnell, and Andrzej Ehrenfeucht. Complete inverted files for efficient text retrieval and analysis. J. ACM, 34(3):578–595, 1987. doi:10.1145/28869.28873.
[5] Dany Breslauer and Zvi Galil. An optimal $o(\log\log n)$ time parallel string matching algorithm. SIAM J. Comput., 19(6):1051–1058, 1990. doi:10.1137/0219072.
[6] Moses Charikar, Eric Lehman, Ding Liu, Rina Panigrahy, Manoj Prabhakaran, Amit Sahai, and Abhi Shelat. The smallest grammar problem. IEEE Trans. Inf. Theory, 51(7):2554–2576, 2005. doi:10.1109/TIT.2005.850116.
[7] Alan M. Cleary and Jordan Dood. Constructing the CDAWG CFG using lcp-intervals. In DCC 2023, pages 178–187, 2023. doi:10.1109/DCC55655.2023.00026.
[8] Maxime Crochemore, F. Mignosi, and A. Restivo. Automata and forbidden words. Information Processing Letters, 67(3):111–117, 1998. doi:10.1016/S0020-0190(98)00104-5.
[9] Hiroto Fujimaru, Yuto Nakashima, and Shunsuke Inenaga. Tight bounds for the sensitivity of CDAWGs with left-end edits. Acta Informatica, 62(12), 2025. doi:10.1007/S00236-025-00478-Y.
[10] Sara Giuliani, Shunsuke Inenaga, Zsuzsanna Lipták, Nicola Prezza, Marinella Sciortino, and Anna Toffanello. Novel results on the number of runs of the Burrows-Wheeler-transform. In SOFSEM, pages 249–262, 2021. doi:10.1007/978-3-030-67731-2_18.
[11] Sara Giuliani, Shunsuke Inenaga, Zsuzsanna Lipták, Giuseppe Romana, Marinella Sciortino, and Cristian Urbina. Bit catastrophes for the Burrows-Wheeler transform. Theory of Computing Systems, 69(19), 2025. doi:10.1007/S00224-024-10212-9.
[12] Peaker Guo, Patrick Eades, Anthony Wirth, and Justin Zobel. Exploiting new properties of string net frequency for efficient computation. In CPM 2024, volume 296 of LIPIcs, pages 16:1–16:16, 2024. doi:10.4230/LIPIcs.CPM.2024.16.
[13] Lucian Ilie and William F Smyth. Minimum unique substrings and maximum repeats. Fundamenta Informaticae, 110(1-4):183–195, 2011. doi:10.3233/FI-2011-536.
[14] Shunsuke Inenaga. Linear-size suffix tries and linear-size CDAWGs simplified and improved. Acta Informatica, 61(4):445–468, 2024. doi:10.1007/S00236-024-00465-9.
[15] Shunsuke Inenaga, Hiromasa Hoshino, Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa, Giancarlo Mauri, and Giulio Pavesi. On-line construction of compact directed acyclic word graphs. Discrete Applied Mathematics, 146(2):156–179, 2005. doi:10.1016/J.DAM.2004.04.012.
[16] Shunsuke Inenaga, Takuya Mieno, Hiroki Arimura, Mitsuru Funakoshi, and Yuta Fujishige. Computing minimal absent words and extended bispecial factors with CDAWG space. In IWOCA 2024, volume 14764 of Lecture Notes in Computer Science, pages 327–340, 2024. doi:10.1007/978-3-031-63021-7_25.
[17] Tomasz Kociumaka, Gonzalo Navarro, and Nicola Prezza. Toward a definitive compressibility measure for repetitive sequences. IEEE Trans. Inf. Theory, 69(4):2074–2092, 2023. doi:10.1109/TIT.2022.3224382.
[18] Guillaume Lagarde and Sylvain Perifel. Lempel-Ziv: a “one-bit catastrophe” but not a tragedy. In SODA, pages 1478–1495, 2018. doi:10.1137/1.9781611975031.97.
[19] William Merrill, Noah A. Smith, and Yanai Elazar. Evaluating n-gram novelty of language models using Rusty-DAWG. In EMNLP 2024, pages 14459–14473, 2024. doi:10.18653/V1/2024.EMNLP-MAIN.800.
[20] Takuya Mieno and Shunsuke Inenaga. Space-efficient online computation of string net occurrences. In CPM 2025, LIPIcs, pages 23:1–23:13, 2025. doi:10.4230/LIPIcs.CPM.2025.23.
[21] Masamichi Miyazaki, Ayumi Shinohara, and Masayuki Takeda. An improved pattern matching algorithm for strings in terms of straight line programs. Journal of Discrete Algorithms, 1(1):187–204, 2000.
[22] Yuto Nakashima, Dominik Köppl, Mitsuru Funakoshi, Shunsuke Inenaga, and Hideo Bannai. Edit and alphabet-ordering sensitivity of lex-parse. In MFCS 2024, volume 306 of LIPIcs, pages 75:1–75:15, 2024. doi:10.4230/LIPIcs.MFCS.2024.75.
[23] Gonzalo Navarro. Computing mems and relatives on repetitive text collections. ACM Trans. Algorithms, 21(1):12:1–12:33, 2025. doi:10.1145/3701561.
[24] Gonzalo Navarro, Carlos Ochoa, and Nicola Prezza. On the approximation ratio of ordered parsings. IEEE Trans. Inf. Theory, 67(2):1008–1026, 2021. doi:10.1109/TIT.2020.3042746.
[25] Jakub Radoszewski and Wojciech Rytter. On the structure of compacted subword graphs of Thue-Morse words and their applications. J. Discrete Algorithms, 11:15–24, 2012. doi:10.1016/J.JDA.2011.01.001.
[26] Wojciech Rytter. Application of Lempel-Ziv factorization to the approximation of grammar-based compression. Theor. Comput. Sci., 302(1-3):211–222, 2003. doi:10.1016/S0304-3975(02)00777-6.
[27] Wojciech Rytter. The structure of subword graphs and suffix trees of Fibonacci words. Theor. Comput. Sci., 363(2):211–223, 2006. doi:10.1016/J.TCS.2006.07.025.
[28] James A. Storer and Thomas G. Szymanski. Data compression via textual substitution. J. ACM, 29(4):928–951, 1982. doi:10.1145/322344.322346.
[29] Masayuki Takeda, Tetsuya Matsumoto, Tomoko Fukuda, and Ichiro 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. doi:10.1007/3-540-44418-1_10.
[30] Peter Weiner. Linear pattern matching algorithms. In Proceedings of the 14th Annual Symposium on Switching and Automata Theory, pages 1–11, 1973. doi:10.1109/SWAT.1973.13.
[31] J. Ziv and A. Lempel. A universal algorithm for sequential data compression. IEEE Transactions on Information Theory, 23(3):337–343, 1977. doi:10.1109/TIT.1977.1055714.
[32] Jacob Ziv and Abraham Lempel. Compression of individual sequences via variable-rate coding. IEEE Trans. Inf. Theory, 24(5):530–536, 1978. doi:10.1109/TIT.1978.1055934.

[bib.bib1] [1] Tooru Akagi, Mitsuru Funakoshi, and Shunsuke Inenaga. Sensitivity of string compressors and repetitiveness measures. Information and Computation, 291:104999, 2023. doi:10.1016/J.IC.2022.104999.

[bib.bib2] [2] Pawel Baturo, Marcin Piatkowski, and Wojciech Rytter. Usefulness of directed acyclic subword graphs in problems related to Standard Sturmian Words. Int. J. Found. Comput. Sci., 20(6):1005–1023, 2009. doi:10.1142/S0129054109007017.

[bib.bib3] [3] Djamal Belazzougui and Fabio Cunial. Fast label extraction in the CDAWG. In SPIRE 2017, pages 161–175, 2017. doi:10.1007/978-3-319-67428-5_14.

[bib.bib4] [4] Anselm Blumer, J. Blumer, David Haussler, Ross McConnell, and Andrzej Ehrenfeucht. Complete inverted files for efficient text retrieval and analysis. J. ACM, 34(3):578–595, 1987. doi:10.1145/28869.28873.

[bib.bib5] [5] Dany Breslauer and Zvi Galil. An optimal $o(\log\log n)$ time parallel string matching algorithm. SIAM J. Comput., 19(6):1051–1058, 1990. doi:10.1137/0219072.

[bib.bib6] [6] Moses Charikar, Eric Lehman, Ding Liu, Rina Panigrahy, Manoj Prabhakaran, Amit Sahai, and Abhi Shelat. The smallest grammar problem. IEEE Trans. Inf. Theory, 51(7):2554–2576, 2005. doi:10.1109/TIT.2005.850116.

[bib.bib7] [7] Alan M. Cleary and Jordan Dood. Constructing the CDAWG CFG using lcp-intervals. In DCC 2023, pages 178–187, 2023. doi:10.1109/DCC55655.2023.00026.

[bib.bib8] [8] Maxime Crochemore, F. Mignosi, and A. Restivo. Automata and forbidden words. Information Processing Letters, 67(3):111–117, 1998. doi:10.1016/S0020-0190(98)00104-5.

[bib.bib9] [9] Hiroto Fujimaru, Yuto Nakashima, and Shunsuke Inenaga. Tight bounds for the sensitivity of CDAWGs with left-end edits. Acta Informatica, 62(12), 2025. doi:10.1007/S00236-025-00478-Y.

[bib.bib10] [10] Sara Giuliani, Shunsuke Inenaga, Zsuzsanna Lipták, Nicola Prezza, Marinella Sciortino, and Anna Toffanello. Novel results on the number of runs of the Burrows-Wheeler-transform. In SOFSEM, pages 249–262, 2021. doi:10.1007/978-3-030-67731-2_18.

[bib.bib11] [11] Sara Giuliani, Shunsuke Inenaga, Zsuzsanna Lipták, Giuseppe Romana, Marinella Sciortino, and Cristian Urbina. Bit catastrophes for the Burrows-Wheeler transform. Theory of Computing Systems, 69(19), 2025. doi:10.1007/S00224-024-10212-9.

[bib.bib12] [12] Peaker Guo, Patrick Eades, Anthony Wirth, and Justin Zobel. Exploiting new properties of string net frequency for efficient computation. In CPM 2024, volume 296 of LIPIcs, pages 16:1–16:16, 2024. doi:10.4230/LIPIcs.CPM.2024.16.

[bib.bib13] [13] Lucian Ilie and William F Smyth. Minimum unique substrings and maximum repeats. Fundamenta Informaticae, 110(1-4):183–195, 2011. doi:10.3233/FI-2011-536.

[bib.bib14] [14] Shunsuke Inenaga. Linear-size suffix tries and linear-size CDAWGs simplified and improved. Acta Informatica, 61(4):445–468, 2024. doi:10.1007/S00236-024-00465-9.

[bib.bib15] [15] Shunsuke Inenaga, Hiromasa Hoshino, Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa, Giancarlo Mauri, and Giulio Pavesi. On-line construction of compact directed acyclic word graphs. Discrete Applied Mathematics, 146(2):156–179, 2005. doi:10.1016/J.DAM.2004.04.012.

[bib.bib16] [16] Shunsuke Inenaga, Takuya Mieno, Hiroki Arimura, Mitsuru Funakoshi, and Yuta Fujishige. Computing minimal absent words and extended bispecial factors with CDAWG space. In IWOCA 2024, volume 14764 of Lecture Notes in Computer Science, pages 327–340, 2024. doi:10.1007/978-3-031-63021-7_25.

[bib.bib17] [17] Tomasz Kociumaka, Gonzalo Navarro, and Nicola Prezza. Toward a definitive compressibility measure for repetitive sequences. IEEE Trans. Inf. Theory, 69(4):2074–2092, 2023. doi:10.1109/TIT.2022.3224382.

[bib.bib18] [18] Guillaume Lagarde and Sylvain Perifel. Lempel-Ziv: a “one-bit catastrophe” but not a tragedy. In SODA, pages 1478–1495, 2018. doi:10.1137/1.9781611975031.97.

[bib.bib19] [19] William Merrill, Noah A. Smith, and Yanai Elazar. Evaluating n-gram novelty of language models using Rusty-DAWG. In EMNLP 2024, pages 14459–14473, 2024. doi:10.18653/V1/2024.EMNLP-MAIN.800.

[bib.bib20] [20] Takuya Mieno and Shunsuke Inenaga. Space-efficient online computation of string net occurrences. In CPM 2025, LIPIcs, pages 23:1–23:13, 2025. doi:10.4230/LIPIcs.CPM.2025.23.

[bib.bib21] [21] Masamichi Miyazaki, Ayumi Shinohara, and Masayuki Takeda. An improved pattern matching algorithm for strings in terms of straight line programs. Journal of Discrete Algorithms, 1(1):187–204, 2000.

[bib.bib22] [22] Yuto Nakashima, Dominik Köppl, Mitsuru Funakoshi, Shunsuke Inenaga, and Hideo Bannai. Edit and alphabet-ordering sensitivity of lex-parse. In MFCS 2024, volume 306 of LIPIcs, pages 75:1–75:15, 2024. doi:10.4230/LIPIcs.MFCS.2024.75.

[bib.bib23] [23] Gonzalo Navarro. Computing mems and relatives on repetitive text collections. ACM Trans. Algorithms, 21(1):12:1–12:33, 2025. doi:10.1145/3701561.

[bib.bib24] [24] Gonzalo Navarro, Carlos Ochoa, and Nicola Prezza. On the approximation ratio of ordered parsings. IEEE Trans. Inf. Theory, 67(2):1008–1026, 2021. doi:10.1109/TIT.2020.3042746.

[bib.bib25] [25] Jakub Radoszewski and Wojciech Rytter. On the structure of compacted subword graphs of Thue-Morse words and their applications. J. Discrete Algorithms, 11:15–24, 2012. doi:10.1016/J.JDA.2011.01.001.

[bib.bib26] [26] Wojciech Rytter. Application of Lempel-Ziv factorization to the approximation of grammar-based compression. Theor. Comput. Sci., 302(1-3):211–222, 2003. doi:10.1016/S0304-3975(02)00777-6.

[bib.bib27] [27] Wojciech Rytter. The structure of subword graphs and suffix trees of Fibonacci words. Theor. Comput. Sci., 363(2):211–223, 2006. doi:10.1016/J.TCS.2006.07.025.

[bib.bib28] [28] James A. Storer and Thomas G. Szymanski. Data compression via textual substitution. J. ACM, 29(4):928–951, 1982. doi:10.1145/322344.322346.

[bib.bib29] [29] Masayuki Takeda, Tetsuya Matsumoto, Tomoko Fukuda, and Ichiro 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. doi:10.1007/3-540-44418-1_10.

[bib.bib30] [30] Peter Weiner. Linear pattern matching algorithms. In Proceedings of the 14th Annual Symposium on Switching and Automata Theory, pages 1–11, 1973. doi:10.1109/SWAT.1973.13.

[bib.bib31] [31] J. Ziv and A. Lempel. A universal algorithm for sequential data compression. IEEE Transactions on Information Theory, 23(3):337–343, 1977. doi:10.1109/TIT.1977.1055714.

[bib.bib32] [32] Jacob Ziv and Abraham Lempel. Compression of individual sequences via variable-rate coding. IEEE Trans. Inf. Theory, 24(5):530–536, 1978. doi:10.1109/TIT.1978.1055934.

Constant Multiplicative Sensitivity on the CDAWGs

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Compression sensitivity.

2 Preliminaries

Strings.

Maximal substrings and maximal repeats.

CDAWG.

Sensitivity of CDAWG size and our results.

Theorem 1.

3 Occurrences of maximal repeats crossing the edited position

Definition 2 (Crossing occurrences).

Definition 3.

Definition 4 (Partition of new maximal repeats).

Definition 5.

Example 6.

4 Upper bound for total out-degrees of nodes w.r.t. 𝗡𝟏∪𝗡𝟑⁢𝐀

Lemma 7.

Proof.

Lemma 8.

Proof.

Lemma 9.

Proof.

4.1 Correspondence between 𝗡𝟏∪𝗡𝟑⁢𝐀 and 𝗠⁢(𝑻)

Definition 10.

Lemma 11.

Proof.

Case (a) 𝒙∈𝗡𝟏.

Case (b) 𝒙∈𝗡𝟑⁢𝐀 and 𝒙 is of Type (𝐢), (𝐢𝐢) or (𝐢𝐯).

Case (c) 𝒙∈𝗡𝟑⁢𝐀 and 𝒙 is of Type (𝐢𝐢𝐢).

Case (d) 𝒙∈𝗡𝟑⁢𝐀 and 𝒙 is of Type (𝐯).

Lemma 12.

Proof.

4.2 Upper bound w.r.t. 𝗡𝟏∪𝗡𝟑⁢𝐀

Lemma 13.

Proof.

5 Upper bound for total out-degrees of nodes w.r.t. 𝗡𝟐∪𝗤

Lemma 14.

Proof.

Lemma 15.

Proof.

Lemma 16.

Proof.

5.1 Correspondence between 𝗡𝟐∪𝗤𝟏 and 𝗠⁢(𝑻)

Definition 17.

Lemma 18.

Proof.

Lemma 19.

Proof.

5.2 Upper bound w.r.t. 𝗡𝟐∪𝗤

Lemma 20.

Proof.

When 𝒙∈𝗡𝟐 and 𝑯⁢(𝒙),𝑰⁢(𝒙)≠𝑻.

When 𝒙∈𝗡𝟐 and 𝑯⁢(𝒙)=𝑻 or 𝑰⁢(𝒙)=𝑻.

When 𝒙∈𝗤𝟏 and 𝑯⁢(𝒙),𝑰⁢(𝒙)≠𝑻.

When 𝒙∈𝗤𝟏 and 𝑯⁢(𝒙)=𝑻 or 𝑰⁢(𝒙)=𝑻.

Wrapping up.

6 Upper bound for total out-degrees of nodes w.r.t. 𝗡𝟑⁢𝐁

Definition 21.

Lemma 22.

Proof.

6.1 Correspondence between 𝗡𝟑⁢𝐁 and 𝗠⁢(𝑻)

Definition 23.

Lemma 24.

Proof.

6.2 Upper bound w.r.t. 𝗡𝟑⁢𝐁

Lemma 25.

Proof.

7 Tighter upper bound for strings ending with $

Lemma 26.

Proof.

8 Conclusions

4 Upper bound for total out-degrees of nodes w.r.t. $\mathsf{N}_{\mathrm{1}}\cup\mathsf{N}_{\mathrm{3A}}$

4.1 Correspondence between $\mathsf{N}_{\mathrm{1}}\cup\mathsf{N}_{\mathrm{3A}}$ and $\mathsf{M}(T)$

Case (a) $x\in\mathsf{N}_{\mathrm{1}}$ .

Case (b) $x\in\mathsf{N}_{\mathrm{3A}}$ and $𝒙$ is of Type $\rm{(i)}$ , $\rm{(ii)}$ or $\rm{(iv)}$ .

Case (c) $x\in\mathsf{N}_{\mathrm{3A}}$ and $𝒙$ is of Type $\rm{(iii)}$ .

Case (d) $x\in\mathsf{N}_{\mathrm{3A}}$ and $𝒙$ is of Type $\rm{(v)}$ .

4.2 Upper bound w.r.t. $\mathsf{N}_{\mathrm{1}}\cup\mathsf{N}_{\mathrm{3A}}$

5 Upper bound for total out-degrees of nodes w.r.t. $\mathsf{N}_{\mathrm{2}}\cup\mathsf{Q}$

5.1 Correspondence between $\mathsf{N}_{\mathrm{2}}\cup\mathsf{Q}_{\mathrm{1}}$ and $\mathsf{M}(T)$

5.2 Upper bound w.r.t. $\mathsf{N}_{\mathrm{2}}\cup\mathsf{Q}$

When $x\in\mathsf{N}_{\mathrm{2}}$ and $H(x),I(x)\neq T$ .

When $x\in\mathsf{N}_{\mathrm{2}}$ and $H(x)=T$ or $I(x)=T$ .

When $x\in\mathsf{Q}_{\mathrm{1}}$ and $H(x),I(x)\neq T$ .

When $x\in\mathsf{Q}_{\mathrm{1}}$ and $H(x)=T$ or $I(x)=T$ .

6 Upper bound for total out-degrees of nodes w.r.t. $\mathsf{N}_{\mathrm{3B}}$

6.1 Correspondence between $\mathsf{N}_{\mathrm{3B}}$ and $\mathsf{M}(T)$

6.2 Upper bound w.r.t. $\mathsf{N}_{\mathrm{3B}}$