# Internal Shortest Absent Word Queries in Constant Time and Linear
Space111The present paper is an extended and improved version of an earlier
text that appeared in the 32nd Annual Symposium on Combinatorial Pattern
Matching, CPM 2021 [8].

Golnaz Badkobeh<EMAIL_ADDRESS>Panagiotis Charalampopoulos222Supported
by the Israel Science Foundation grant 592/17.
<EMAIL_ADDRESS>Dmitry Kosolobov333Supported by the
Ministry of Science and Higher Education of the Russian Federation (Ural
Mathematical Center project No. 075-02-2021-1387<EMAIL_ADDRESS>Solon P.
Pissis<EMAIL_ADDRESS>Department of Computing, Goldsmiths University of
London, UK  Efi Arazi School of Computer Science, The Interdisciplinary Center
Herzliya, Israel  Ural Federal University, Ekaterinburg, Russia  CWI,
Amsterdam, The Netherlands  Vrije Universiteit, Amsterdam, The Netherlands

###### Abstract

Given a string $T$ of length $n$ over an alphabet
$\Sigma\subset\\{1,2,\ldots,n^{\mathcal{O}(1)}\\}$ of size $\sigma$, we are to
preprocess $T$ so that given a range $[i,j]$, we can return a representation
of a shortest string over $\Sigma$ that is absent in the fragment $T[i]\cdots
T[j]$ of $T$. We present an $\mathcal{O}(n)$-space data structure that answers
such queries in constant time and can be constructed in
$\mathcal{O}(n\log_{\sigma}n)$ time.

###### keywords:

string algorithms , internal queries , shortest absent word , bit parallelism

##  1 Introduction

Range queries are a classic data structure topic [59, 12, 11]. In 1d, a range
query $q=f(A,i,j)$ on an array of $n$ elements over some set $U$, denoted by
$A[1\mathinner{.\,.}n]$, takes two indices $1\leq i\leq j\leq n$, a function
$f$ defined over arrays of elements of $U$, and outputs
$f(A[i\mathinner{.\,.}j])=f(A[i],\ldots,A[j])$. Range query data structures in
1d can thus be viewed as data structures answering queries on a string in the
internal setting, where $U$ is the considered alphabet.

Internal queries on a string have received much attention in recent years. In
the internal setting, we are asked to preprocess a string $T$ of length $n$
over an alphabet $\Sigma$ of size $\sigma$, so that queries about substrings
of $T$ can be answered efficiently. Note that an arbitrary substring of $T$
can be encoded in $\mathcal{O}(1)$ words of space by the indices $i,j$ of its
occurrence as a fragment $T[i]\cdots T[j]=T[i\mathinner{.\,.}j]$ of $T$. Data
structures for answering internal queries are interesting in their own right,
but also have numerous applications in the design of algorithms and (more
sophisticated) data structures. Because of these numerous applications, we
usually place particular emphasis on the construction time—other than on the
tradeoff between space and query time, which is the main focus in the classic
data structure literature.

In data structures on strings it is typically assumed that the input alphabet
is integer and polynomially bounded, i.e., it is a subset of
$\\{1,2,\ldots,n^{\mathcal{O}(1)}\\}$ where $n$ is the length of the input
string $T$. One of the most widely-used internal queries is that of asking for
the _longest common prefix_ of two suffixes $T[i\mathinner{.\,.}n]$ and
$T[j\mathinner{.\,.}n]$ of $T$. The classic data structure for this problem
[45] consists of the suffix tree of $T$ [25] and a lowest common ancestor data
structure [37] over the suffix tree. It occupies $\mathcal{O}(n)$ space, it
can be constructed in $\mathcal{O}(n)$ time, and it answers queries in
$\mathcal{O}(1)$ time. In the word RAM model of computation with word size
$\Theta(\log n)$ bits the construction time is not necessarily optimal when
the input alphabet is $\\{1,2,\ldots,\sigma\\}$ and the string is packed into
$\mathcal{O}(n/\log_{\sigma}n)$ machine words. A sequence of works [57, 49,
13] has culminated in the recent optimal data structure of Kempa and Kociumaka
[40]: it occupies $\mathcal{O}(n/\log_{\sigma}n)$ space, it can be constructed
in $\mathcal{O}(n/\log_{\sigma}n)$ time, and it answers queries in
$\mathcal{O}(1)$ time.

Another fundamental problem in this setting is the _internal pattern matching_
(IPM) problem. It consists in preprocessing $T$ so that we can efficiently
compute the occurrences of a substring $U$ of $T$ in another substring $V$ of
$T$. For the decision version of the IPM problem, Keller et al. [39] presented
a data structure of nearly-linear size supporting sublogarithmic-time queries.
Kociumaka et al. [44] presented a data structure of linear size supporting
constant-time queries when the ratio between the lengths of $V$ and $U$ is
bounded by a constant. The $\mathcal{O}(n)$-time construction algorithm of the
latter data structure was derandomized in [42]. In fact, Kociumaka et al.
[44], using their efficient IPM queries as a subroutine, managed to show
efficient solutions for other internal problems, such as for computing the
periods of a substring (_period queries_ , introduced in [43]), and for
checking whether two substrings are rotations of one another (_cyclic
equivalence queries_). Other problems that have been studied in the internal
setting include string alignment [58, 18], approximate pattern matching [21],
dictionary matching [20, 19], longest common substring [4], counting
palindromes [55], range longest common prefix [3, 1, 46, 34], the computation
of the lexicographically minimal or maximal suffix, and minimal rotation [6,
41], as well as of the lexicographically $k$th suffix [7]. We refer the
interested reader to the Ph.D dissertation of Kociumaka [42], for a nice
exposition.

In this work, we extend this line of research by investigating the following
basic internal query, which, to the best of our knowledge, has not been
studied previously. Given a string $T$ of length $n$ over an alphabet
$\Sigma\subset\\{1,2,\ldots,n^{\mathcal{O}(1)}\\}$, preprocess $T$ so that
given a range $[i,j]$, we can return a shortest string over $\Sigma$ that does
not occur in $T[i\mathinner{.\,.}j]$. The latter shortest string is also known
as a shortest absent word in the literature. We work on the standard unit-cost
word RAM model with machine word-size $w=\Theta(\log n)$ bits. We measure the
space used by our algorithms and data structures in machine words, unless
stated otherwise. We assume that we have random access to $T$ and so our
algorithms return a constant-space representation of a shortest string (a
witness) consisting of a substring of $T$ and a letter. A naïve solution for
this problem precomputes a table of size $\mathcal{O}(n^{2})$ that stores the
answer for every possible query $[i,j]$. Our main result is the following
theorem.

theoremmainthm Given a string $T$ of length $n$ over an alphabet
$\Sigma\subset\\{1,2,\ldots,n^{\mathcal{O}(1)}\\}$ of size $\sigma$, we can
construct in $\mathcal{O}(n\log_{\sigma}n)$ time a data structure of size
$\mathcal{O}(n)$ that, for any given query $[a,b]$, can compute in
$\mathcal{O}(1)$ time a shortest string over $\Sigma$ that does not occur in
$T[a\mathinner{.\,.}b]$.

In an earlier conference version of the present paper [8], we have obtained a
weaker result: a data structure of size
$\mathcal{O}((n/k)\cdot\log\log_{\sigma}n)$ that can answer queries in
$\mathcal{O}(\log\log_{\sigma}k)$ time, where $k$ is a user-defined parameter
from $[1,\log\log_{\sigma}n]$. The improved data structure presented in this
manuscript combines ideas from the conference version and the utilization of
succinct fusion trees introduced by Grossi et al. [36].

In the related _range shortest unique substring_ problem, defined by Abedin et
al. [2], the task is to construct a data structure over $T$ to be able to
answer the following type of online queries efficiently. Given a range
$[i,j]$, return a shortest string with exactly one occurrence (starting
position) in $[i,j]$. Abedin et al. presented a data structure of size
$\mathcal{O}(n\log n)$ supporting $\mathcal{O}(\log_{w}n)$-time queries, where
$w=\Theta(\log n)$ is the word size. Additionally, Abedin et al. [2] presented
a data structure of size $\mathcal{O}(n)$ supporting
$\mathcal{O}(\sqrt{n}\log^{\epsilon}n)$-time queries, where $\epsilon$ is an
arbitrarily small positive constant.

### Our Techniques

For clarity of exposition, in this overview, we skip the time-efficient
construction algorithms of our data structures and only describe how to
compute the _length_ of a shortest absent word (without a witness) in
$T[a\mathinner{.\,.}b]$; note that this length is at most $\log_{\sigma}n$.
Let us also recall that the length of a shortest absent word of $T$ can be
computed in $\mathcal{O}(n)$ time using the suffix tree of $T$ [25]. It
suffices to traverse the suffix tree of $T$ recording the shortest string-
depth $\ell$, where an implicit or explicit node has less than $\sigma$
outgoing edges.

_First approach:_ We precompute, for each position $i$ and for each length
$j\in[1,\log_{\sigma}n]$, the starting position of the shortest suffix of
$T[1\mathinner{.\,.}i]$ that contains an occurrence of each of the
$\sigma^{j}$ distinct words of length $j$. Then, a query for the length of a
shortest absent word of $T[a\mathinner{.\,.}b]$ reduces to computing the
predecessor of $a$ among the starting positions we have precomputed for
position $b$. By maintaining these $\mathcal{O}(\log_{\sigma}n)$ starting
positions in a fusion tree [32], we obtain a data structure of size
$\mathcal{O}(n\log_{\sigma}n)$ supporting queries in $\mathcal{O}(\log_{w}\log
n)=\mathcal{O}(1)$ time.

_Second approach:_ We precompute, for each length $j\in[1,\log_{\sigma}n]$,
all minimal fragments of $T$ that contain an occurrence of each of the
distinct $\sigma^{j}$ words of length $j$. As these fragments are inclusion-
free, we can encode them using two $n$-bit arrays storing their starting and
ending positions in $T$, respectively. We thus require $\mathcal{O}(n)$ words
of space in total over all $j$s. Observe that $T[a\mathinner{.\,.}b]$ does not
have an absent word of length $j$ if and only if it contains a minimal
fragment for length $j$; we can check this condition in $\mathcal{O}(1)$ time
after augmenting the computed bit arrays with succinct rank and select data
structures [38]. Finally, due to monotonicity (if $T[a\mathinner{.\,.}b]$
contains all strings of length $j+1$ then $T$ contains all strings of length
$j$), we can binary search for the answer in $\mathcal{O}(\log\log_{\sigma}n)$
time.

_Third approach:_ We optimize the first approach by utilizing succinct fusion
trees to store the sets of size $\mathcal{O}(\log_{\sigma}n)$ associated with
positions of $T$, thus reducing the space on top of the sets to
$\mathcal{O}(n\log_{\sigma}\log n)$. Instead of storing the
$\mathcal{O}(\log_{\sigma}n)$-size sets explicitly, we compute their elements
on demand using $\mathcal{O}(\log_{\sigma}n)$ select data structures, each
occupying $\mathcal{O}(n)$ bits. This leads to an
$\mathcal{O}(n\log_{\sigma}\log n)$-space solution. In order to optimize it
further, we rely on the following combinatorial observation: if the length of
a shortest absent word of a string $X$ over $\Sigma$ is $\lambda$, we need to
append $\Omega(\sigma^{d-1}\cdot\lambda)$ letters to $X$ in order to obtain a
string with a shortest absent word of length $\lambda+d$. (For intuition,
think of $|X|$ as a constant; then, we essentially need to append the de
Bruijn sequence of order $d$ over $\Sigma$ to $X$ in order to achieve the
desired result.) This observation allows us to lower the memory consumption by
truncating all succinct fusion trees at positions that are not multiples of
$\log\log n$, by building them only for their first $\mathcal{O}(\log
n/\log\log n)$ entries. The total space thus reduces to $\mathcal{O}(n)$
words. A query for the length of a shortest absent word of
$T[a\mathinner{.\,.}b]$ is performed by first checking whether the answer is
at most $\log n/\log\log n$, which is done using the (truncated) fusion tree
stored at $b$, and, if not, a query on $T[a\mathinner{.\,.}b^{\prime}]$ is
performed, where $b^{\prime}$ is the closest multiple of $\log\log n$ after
$b$. It can be shown using the combinatorial observation that the answer for
$T[a\mathinner{.\,.}b]$ is within an $\mathcal{O}(1)$-length range of the
answer for $T[a\mathinner{.\,.}b^{\prime}]$, and it is computed by the data
structure from the second approach.

### Other Related Work

Let us recall that a string $S$ that does not occur in $T$ is called _absent_
from $T$, and if all its proper substrings appear in $T$ it is called a
_minimal absent word_ of $T$. It should be clear that every shortest absent
word is also a minimal absent word. Minimal absent words (MAWs) are used in
many applications [56, 53, 28, 35, 14, 51, 24] and their theory is well
developed [48, 27, 29], also from an algorithmic and data structure point of
view [47, 22, 9, 17, 16, 5, 33, 10, 23]. For example, it is well known that,
given two strings $X$ and $Y$, one has $X=Y$ if and only if $X$ and $Y$ have
the same set of MAWs [48].

### Paper Organization

Section 2 provides some preliminaries. The first approach is detailed in
Section 3 and the second one in Section 4. Section 5 provides the
combinatorial foundations for the third approach, which is detailed in Section
6. Sections 3–5 have essentially already appeared in the conference version
[8] of our paper; the main difference and novelty lie in Section 6. We
conclude with open problems in Section 7.

##  2 Preliminaries

An _alphabet_ $\Sigma$ is a finite nonempty set whose elements are called
_letters_. A string (or _word_) $S=S[1\mathinner{.\,.}n]$ is a sequence of
_length_ $|S|=n$ over $\Sigma$. The empty string $\varepsilon$ is the string
of length $0$. The _concatenation_ of two strings $S$ and $T$ is the string
composed of the letters of $S$ followed by the letters of $T$; it is denoted
by $S\cdot T$ or simply by $ST$. The set of all strings (including
$\varepsilon$) over $\Sigma$ is denoted by $\Sigma^{*}$. The set of all
strings of length $k>0$ over $\Sigma$ is denoted by $\Sigma^{k}$. For $1\leq
i\leq j\leq n$, $S[i]$ denotes the $i$th letter of $S$, and the fragment
$S[i\mathinner{.\,.}j]$ denotes an _occurrence_ of the underlying _substring_
$P=S[i]\cdots S[j]$. We say that $P$ occurs at (starting) _position_ $i$ in
$S$. A string $P$ is called _absent_ from $S$ if it does not occur in $S$. A
substring $S[i\mathinner{.\,.}j]$ is a _suffix_ of $S$ if $j=n$ and it is a
_prefix_ of $S$ if $i=1$.

The following proposition is straightforward (as explained in Section 1).

######  Proposition 1.

Let $T$ be a string of length $n$ over an alphabet
$\Sigma\subset\\{1,2,\ldots,n^{\mathcal{O}(1)}\\}$. A shortest absent word of
$T$ can be computed in $\mathcal{O}(n)$ time.

Given an array $A$ of $n$ items taken from a totally ordered set, the _range
minimum query_ $\textsf{RMQ}_{A}(\ell,r)=\operatorname*{arg\,min}A[k]$ (with
$1\leq\ell\leq k\leq r\leq n$) returns the position of the minimal element in
$A[\ell\mathinner{.\,.}r]$. The following result is known.

######  Theorem 1 ([11, 31]).

Let $A$ be an array of $n$ integers. A data structure of size $2n+o(n)$ bits
that supports RMQs on $A$ in $\mathcal{O}(1)$ time without the need to store
and access $A$ itself can be constructed in $\mathcal{O}(n)$ time.

We make use of rank and select data structures constructed over bit vectors.
For a bit vector $H$ we define
$\textsf{rank}_{q}(i,H)=|\\{k\in[1,i]:H[k]=q\\}|$ and
$\textsf{select}_{q}(i,H)=\min\\{k\in[1,n]:\textsf{rank}_{q}(k,H)=i\\}$, for
$q\in\\{0,1\\}$. The following result is known.

######  Theorem 2 ([38, 50]).

Let $H$ be a bit vector of $n$ bits. A data structure of $o(n)$ additional
bits that supports rank and select queries on $H$ in $\mathcal{O}(1)$ time can
be constructed in $\mathcal{O}(n)$ time.

The _static predecessor_ problem consists in preprocessing a set $Y$ of
integers, over an ordered universe $U$, so that, for any integer $x\in U$ one
can efficiently return the predecessor $\textsf{pred}(x):=\max\\{y\in Y:y\leq
x\\}$ of $x$ in $Y$. The successor problem is defined analogously: upon a
queried integer $x\in U$, the successor $\min\\{y\in Y:y\geq x\\}$ of $x$ in
$Y$ is to be returned. Willard and Fredman designed the _fusion tree_ data
structure for this problem [32]. In the dynamic variant of the problem,
updates to $Y$ are interleaved with predecessor and successor queries.
Pătraşcu and Thorup [52] presented a dynamic version of fusion trees, which,
in particular, yields an efficient construction of this data structure.

######  Theorem 3 ([32, 52]).

Let $Y$ be a set of at most $n$ $w$-bit integers. A data structure of size
$\mathcal{O}(n)$ can be constructed in $\mathcal{O}(n\log_{w}n)$ time
supporting insertions, deletions, and predecessor queries on $Y$ in
$\mathcal{O}(\log_{w}n)$ time.

We also use a succinct version of the (static) fusion tree that utilizes only
$\mathcal{O}(n\log w)$ _bits_ on top of a read-only array $Y$ of length $n$
(in contrast, the fusion tree from Theorem 3 uses $\mathcal{O}(nw)$ _bits_).
In this data structure there is no need to store the array $Y$ explicitly.
Instead, $Y$ can be “emulated” by computing its elements on demand in
$\mathcal{O}(1)$ time. Albeit it is not explicitly stated in [36, 15], it
follows from their construction that the succinct version can be constructed
from a (usual) fusion tree in linear time.

######  Theorem 4 ([36, 15]).

Let $Y$ be a read-only array of at most $n$ $w$-bit integers and $n\leq
w^{\mathcal{O}(1)}$. A data structure of size $\mathcal{O}(n\log w)$ bits can
be constructed in $\mathcal{O}(n\log_{w}n)$ time supporting predecessor
queries on the elements of $Y$ in $\mathcal{O}(\log_{w}n)$ time, provided that
a table computable in $o(2^{w})$ time and independent of the array has been
precomputed.

Note that if we build multiple predecessor queries for sets of $w$-bit
integers using the above theorem, they can all share a unique table computable
in $o(2^{w})$ time.

If $|U|=\mathcal{O}(n)$, then, after an $\mathcal{O}(n)$-time preprocessing,
we can answer predecessor queries over the integer universe $U$ in
$\mathcal{O}(1)$ time as follows. For each $y\in Y$, we set the $y$th bit of
an initially all-zeros $|U|$-size bit vector. We then preprocess this bit
vector as in Theorem 2. Then, a predecessor query for any integer $x$ can be
answered in $\mathcal{O}(1)$ time due to the following readily verifiable
formula: $\textsf{pred}(x)=\textsf{select}_{1}(\textsf{rank}_{1}(x))$.

The main problem considered in this paper is formally defined as follows.

Internal Shortest Absent Word (ISAW)
Input: A string $T$ of length $n$ over an alphabet
$\Sigma\subset\\{1,2,\ldots,n^{\mathcal{O}(1)}\\}$ of size $\sigma>1$. Output:
Given integers $a$ and $b$, with $1\leq a\leq b\leq n$, output a shortest
string in $\Sigma^{*}$ with no occurrence in $T[a\mathinner{.\,.}b]$.

If $a=b$ then the answer is trivial. So, in what follows we assume that $a<b$.
Let us also remark that the output (shortest absent word) can be represented
in $\mathcal{O}(1)$ space using: either a range $[i,j]\subseteq[1,n]$ and a
letter $\alpha$ of $\Sigma$, such that the shortest string in $\Sigma^{*}$
with no occurrence in $T[a\mathinner{.\,.}b]$ is
$T[i\mathinner{.\,.}j]\alpha$; or simply a range $[i,j]\subseteq[1,n]$ such
that the shortest string in $\Sigma^{*}$ with no occurrence in
$T[a\mathinner{.\,.}b]$ is $T[i\mathinner{.\,.}j]$.

######  Example 1.

Given the string
$T=\texttt{abaabaa{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}abbabbb}aaab}$
and the range $[a,b]=[8,14]$ (shown in red), the only shortest absent word of
$T[8\mathinner{.\,.}14]$ is
$T[i\mathinner{.\,.}j]=T[7\mathinner{.\,.}8]=\texttt{aa}$.

##  3 $\mathcal{O}(n\log_{\sigma}n)$ Space and $\mathcal{O}(1)$ Query Time

Let $T$ be a string of length $n$. We define $S_{T}(j)$ as the function
counting the cardinality of the set of length-$j$ substrings of $T$. This is
known as the _substring complexity_ function [26, 54]. Note that $S_{T}(j)\leq
n$, for all $j$. We have the following simple fact.

######  Fact 5.

The length $\ell$ of a shortest absent word of a string $T$ of length $n$ over
an alphabet of size $\sigma$ is equal to the smallest $j$ for which
$S_{T}(j)<\sigma^{j}$ and hence $\ell\in[1,\lfloor\log_{\sigma}n\rfloor]$.

We denote the set of shortest absent words of $T$ by $\text{SAW}_{T}$. Recall
that, by Proposition 1, a shortest absent word of $T$ can be computed in
$\mathcal{O}(n)$ time. We denote the length of the shortest absent words of
$T$ by $\ell$. By Fact 5, $\ell\leq\lfloor\log_{\sigma}n\rfloor$. Since $\ell$
is an upper bound on the length of the answer for any ISAW query on $T$, in
what follows, we consider only lengths in $[1,\ell-1]$. Let one such length be
denoted by $j$. By constructing and traversing the suffix tree of $T$, we can
assign to each $T[i\mathinner{.\,.}i+j-1]$ its lexicographic rank in
$\Sigma^{j}$. The time required for each length $j$ is $\mathcal{O}(n)$, since
the suffix tree of $T$ can be constructed within this time [25]. Thus, the
total time for all lengths $j\in[1,\ell-1]$ is $\mathcal{O}(n\log_{\sigma}n)$
by Fact 5.

We design the following warm-up solution to the ISAW problem. For all
$j\in[1,\ell-1]$ we store an array $\textsf{RNK}_{j}$ of $n$ integers such
that $\textsf{RNK}_{j}[i]$ is equal to the lexicographic rank of
$T[i\mathinner{.\,.}i+j-1]$ in $\Sigma^{j}$. Then, given a range $[a,b]$, in
order to check if there is an absent word of length $j$ in
$T[a\mathinner{.\,.}b]$ we only need to compute the number of distinct
elements in $\textsf{RNK}_{j}[a\mathinner{.\,.}b-j+1]$. It is folklore that
using a persistent segment tree, we can preprocess an array $A$ of $n$
integers in $\mathcal{O}(n\log n)$ time so that upon a range query $[a,b]$ we
can return the number of distinct elements in $A[a\mathinner{.\,.}b]$ in
$\mathcal{O}(\log n)$ time. Thus, we could use this tool as a black box for
every array $\textsf{RNK}_{j}$ resulting, however, in $\Omega(\log n)$-time
queries. We improve upon this solution as follows.

We employ a range minimum query (RMQ) data structure [11] over a slight
modification of $\textsf{RNK}_{j}$. For each $j$, we have an auxiliary
procedure checking whether all strings from $\Sigma^{j}$ occur in
$T[a\mathinner{.\,.}b]$ or not (i.e., it suffices to check whether any
lexicographic rank is absent from the corresponding range). Similar to the
previous solution, we rank the elements of $\Sigma^{j}$ by their lexicographic
order. We append $\textsf{RNK}_{j}$ with all integers in $[1,\sigma^{j}]$. Let
this array be $\textsf{APP}_{j}$. By Fact 5, we have that
$|\textsf{APP}_{j}|\leq 2n$. Then, we construct an array $\textsf{PRE}_{j}$ of
size $|\textsf{APP}_{j}|$: $\textsf{PRE}_{j}[i]$ stores the position of the
rightmost occurrence of $\textsf{APP}_{j}[i]$ in
$\textsf{APP}_{j}[1\mathinner{.\,.}i-1]$ (or $0$ if such an occurrence does
not exist). This can be done in $\mathcal{O}(n)$ time per $j$ by sorting the
list of pairs $(T[i\mathinner{.\,.}i+j-1],i)$, for all $i$, using the suffix
tree of $T$ to assign ranks for $T[i\mathinner{.\,.}i+j-1]$ and then radix
sort to sort the list of pairs.

We now rely on the following fact.

######  Fact 6.

$S_{T[a\mathinner{.\,.}b]}(j)=\sigma^{j}$ if and only if
$\min\\{\textsf{PRE}_{j}[i]:i\in[b-j+2,|\textsf{PRE}_{j}|]\\}\geq a$.

###### Proof.

If the smallest element in
$\textsf{PRE}_{j}[b-j+2\mathinner{.\,.}|\textsf{PRE}_{j}|]$, say
$\textsf{PRE}_{j}[k]$, is such that $\textsf{PRE}_{j}[k]\geq a$, then all
ranks of elements in $\Sigma^{j}$ occur in
$\textsf{APP}_{j}[a\mathinner{.\,.}b-j+1]$. This is because all elements
(ranks) in $\Sigma^{j}$ occur at least once after $b-j+2$ (due to appending
all integers in $[1,\sigma^{j}]$ to $\textsf{RNK}_{j}$), and thus all must
have a representative occurrence after $b-j+2$. Inspect Figure 1 for an
illustration. (The opposite direction is analogous.) ∎

Figure 1: Illustration of the setting in 6.

The following two examples illustrate the construction of arrays
$\textsf{RNK}_{j}$, $\textsf{APP}_{j}$, and $\textsf{PRE}_{j}$ as well as 6.

######  Example 2 (Construction).

Let $T=\tt abaabaaabbabbbaaab$ and $\Sigma=\\{\texttt{a},\texttt{b}\\}$. The
set $\text{SAW}_{T}$ of shortest absent words of $T$ over $\Sigma$, each of
length $\ell=4$, is $\\{\tt aaaa,\tt abab,\tt baba,\tt bbbb\\}$. Arrays
$\textsf{RNK}_{j}$, $\textsf{APP}_{j}$, and $\textsf{PRE}_{j}$, for all
$j\in[1,\ell-1]$, are as depicted in Table 1.

Table 1: Arrays $\textsf{RNK}_{j}$, $\textsf{APP}_{j}$, and $\textsf{PRE}_{j}$
in Example 1.

$i$ | 1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 |  10 |  11 |  12 |  13 |  14 |  15 |  16 |  17 |  18 |  19 |  20 |  21 |  22 |  23 |  24
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$T$ | a |  b |  a |  a |  b |  a |  a |  a |  b |  b |  a |  b |  b |  b |  a |  a |  a |  b |  |  |  |  |  |
$\textsf{RNK}_{1}$ | 1 |  2 |  1 |  1 |  2 |  1 |  1 |  1 |  2 |  2 |  1 |  2 |  2 |  2 |  1 |  1 |  1 |  2 |  |  |  |  |  |
$\textsf{APP}_{1}$ | 1 |  2 |  1 |  1 |  2 |  1 |  1 |  1 |  2 |  2 |  1 |  2 |  2 |  2 |  1 |  1 |  1 |  2 |  1 |  2 |  |  |  |
$\textsf{PRE}_{1}$ | 0 |  0 |  1 |  3 |  2 |  4 |  6 |  7 |  5 |  9 |  8 |  10 |  12 |  13 |  11 |  15 |  16 |  14 |  17 |  18 |  |  |  |
$\textsf{RNK}_{2}$ | 2 |  3 |  1 |  2 |  3 |  1 |  1 |  2 |  4 |  3 |  2 |  4 |  4 |  3 |  1 |  1 |  2 |  |  |  |  |  |  |
$\textsf{APP}_{2}$ | 2 |  3 |  1 |  2 |  3 |  1 |  1 |  2 |  4 |  3 |  2 |  4 |  4 |  3 |  1 |  1 |  2 |  1 |  2 |  3 |  4 |  |  |
$\textsf{PRE}_{2}$ | 0 |  0 |  0 |  1 |  2 |  3 |  6 |  4 |  0 |  5 |  8 |  9 |  12 |  10 |  7 |  15 |  11 |  16 |  17 |  14 |  13 |  |  |
$\textsf{RNK}_{3}$ | 3 |  5 |  2 |  3 |  5 |  1 |  2 |  4 |  7 |  6 |  4 |  8 |  7 |  5 |  1 |  2 |  |  |  |  |  |  |  |
$\textsf{APP}_{3}$ | 3 |  5 |  2 |  3 |  5 |  1 |  2 |  4 |  7 |  6 |  4 |  8 |  7 |  5 |  1 |  2 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  8
$\textsf{PRE}_{3}$ | 0 |  0 |  0 |  1 |  2 |  0 |  3 |  0 |  0 |  0 |  8 |  0 |  9 |  5 |  6 |  7 |  15 |  16 |  4 |  11 |  14 |  10 |  13 |  12

For instance, $\textsf{RNK}_{2}[15]=\textsf{APP}_{2}[15]=1$ denotes that the
lexicographic rank of aa in $\Sigma^{2}$ is $1$; and $\textsf{PRE}_{2}[15]=7$
denotes that the previous rightmost occurrence of aa is at position $7$.

######  Example 3 (Fact 6).

Let $[a,b]=[7,11]$ and $j=2$ (see Example 1). The smallest element in
$\\{\textsf{PRE}_{2}[11],\ldots,\textsf{PRE}_{2}[21]\\}$ is
$\textsf{PRE}_{2}[15]=7\geq a=7$, which corresponds to rank
$\textsf{APP}_{2}[15]=1$. Indeed all other ranks $2,3,4$ have at least one
occurrence within $\textsf{APP}_{2}[7\mathinner{.\,.}11]=1,2,4,3,2$.

To apply Fact 6, we construct, in $\mathcal{O}(n)$ time, an
$\mathcal{O}(n)$-space, $\mathcal{O}(1)$-query-time RMQ data structure over
$\textsf{PRE}_{j}$; see Theorem 1. This results in
$\mathcal{O}(n\ell)=\mathcal{O}(n\log_{\sigma}n)$ preprocessing time and space
over all $j$.

For querying, let us observe that $\sigma^{j}-S_{T[a\mathinner{.\,.}b]}(j)$,
for any $T,a,b$ and increasing $j$, is non-decreasing. We can thus apply
binary search on $j$ to find the smallest length $j$ such that
$S_{T[a\mathinner{.\,.}b]}(j)<\sigma^{j}$. This results in
$\mathcal{O}(\log\ell)=\mathcal{O}(\log\log_{\sigma}n)$ query time. We obtain
the following proposition (retrieving a witness shortest absent word is
detailed later).

######  Proposition 2.

Given a string $T$ of length $n$ over an alphabet
$\Sigma\subset\\{1,2,\ldots,n^{\mathcal{O}(1)}\\}$ of size $\sigma$, we can
construct a data structure of size $\mathcal{O}(n\log_{\sigma}n)$ in
$\mathcal{O}(n\log_{\sigma}n)$ time, so that if query $[a,b]$ is given, we can
compute a shortest string over $\Sigma$ that does not occur in
$T[a\mathinner{.\,.}b]$ in $\mathcal{O}(\log\log_{\sigma}n)$ time.

We further improve the query time via employing fusion trees as follows. We
create a 2d array $\textsf{FTR}[1\mathinner{.\,.}\ell-1][1\mathinner{.\,.}n]$
of integers, where

$\textsf{FTR}[j][i]=\min\\{\textsf{PRE}_{j}[i-j+2],\ldots,\textsf{PRE}_{j}[|\textsf{PRE}_{j}|]\\},$

for all $j\in[1,\ell-1]$ and $i\in[1,n]$. Intuitively, $\textsf{FTR}[j][i]$ is
the rightmost index of $T$ such that $T[\textsf{FTR}[j][i]\mathinner{.\,.}i]$
contains all strings of length $j$ over $\Sigma$ if such an index exists and
$0$ otherwise.

Array FTR can be constructed in
$\mathcal{O}(n\ell)=\mathcal{O}(n\log_{\sigma}n)$ time by scanning each array
$\textsf{PRE}_{j}$ from right to left maintaining the minimum. Within the same
complexities we also maintain satellite information specifying the index
$k\in[i-j+2,|\textsf{PRE}_{j}|]$ where the range minimum $\textsf{FTR}[j][i]$
came from in the sub-array
$\textsf{PRE}_{j}[i-j+2\mathinner{.\,.}|\textsf{PRE}_{j}|]$. We then construct
$n$ fusion trees, one for every collection of $\ell-1$ integers in
$\textsf{FTR}[1\mathinner{.\,.}\ell-1][i]$. This takes total preprocessing
time and space $\mathcal{O}(n\ell)=\mathcal{O}(n\log_{\sigma}n)$ by Theorem 3.
Given the range query $[a,b]$, we need to find the smallest $j\in[1,\ell-1]$
such that $\textsf{FTR}[j][b]<a$. By Theorem 3, we find where the predecessor
of $a$ lies in $\textsf{FTR}[1\mathinner{.\,.}\ell-1][b]$ in
$\mathcal{O}(\log_{w}\ell)$ time, where $w$ is the word size; this time cost
is $\mathcal{O}(1)$ since $w=\Theta(\log n)$.

We finally retrieve a _witness_ shortest absent word as follows. If there is
no $j<\ell$ such that $\textsf{FTR}[j][b]<a$, then we output any shortest
absent word of length $\ell$ of $T$ arbitrarily. If such a $j<\ell$ exists, by
the definition of $\textsf{FTR}[j][b]$, we output
$T[\textsf{FTR}[j][b]\mathinner{.\,.}\textsf{FTR}[j][b]+j-1]$ if
$\textsf{FTR}[j][b]>0$ or $T[k\mathinner{.\,.}k+j-1]$ if
$\textsf{FTR}[j][b]=0$, where $k$ is the index of $\textsf{PRE}_{j}$, where
the minimum came from. Inspect the following illustrative example.

######  Example 4 (Querying).

We construct array FTR for $T$ from Example 1. For a given $[a,b]$ we look up
column $b$, and find the topmost entry whose value is less than $a$. If all
entries have values greater than or equal to $a$, we output any element from
$\text{SAW}_{T}$ arbitrarily.

$i$ | 1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 |  10 |  11 |  12 |  13 |  14 |  15 |  16 |  17 |  18
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$T$ | a |  b |  a |  a |  b |  a |  a |  a |  b |  b |  a |  b |  b |  b |  a |  a |  a |  b
$\textsf{FTR}[1]$ | 0 |  1 |  2 |  2 |  4 |  5 |  5 |  5 |  8 |  8 |  10 |  11 |  11 |  11 |  14 |  14 |  14 |  17
$\textsf{FTR}[2]$ | 0 |  0 |  0 |  0 |  0 |  0 |  0 |  0 |  0 |  5 |  7 |  7 |  7 |  7 |  7 |  11 |  11 |  13
$\textsf{FTR}[3]$ | 0 |  0 |  0 |  0 |  0 |  0 |  0 |  0 |  0 |  0 |  0 |  0 |  0 |  4 |  4 |  4 |  4 |  4

If $[a,b]=[3,14]$ then no entry in column $b=14$ is less than $a=3$, which
means the length of the shortest absent word is 4; we output one from $\\{\tt
aaaa,\tt abab,\tt baba,\tt bbbb\\}$ arbitrarily. If $[a,b]=[5,14]$ then
$\textsf{FTR}[3][14]=4<5$ so the length of a shortest absent word of
$T[5\mathinner{.\,.}14]$ is 3; a shortest absent word is
$T[\textsf{FTR}[3][14]\mathinner{.\,.}\textsf{FTR}[3][14]+3-1]=T[4\mathinner{.\,.}6]=\tt
aba$.

If $[a,b]=[7,9]$, $\textsf{FTR}[2][9]=0<7$ so the length of a shortest absent
word is $2$; a shortest absent word is
$T[k\mathinner{.\,.}k+j-1]=T[9\mathinner{.\,.}10]=\tt bb$ because
$\textsf{FTR}[2][9]=\min\\{\textsf{PRE}_{2}[9],\ldots,\textsf{PRE}_{2}[|\textsf{PRE}_{2}|]\\}=\textsf{PRE}_{2}[9]=0$
tells us that the minimum in this range came from index $k=9$.

We obtain the following proposition.

######  Proposition 3.

Given a string $T$ of length $n$ over an alphabet
$\Sigma\subset\\{1,2,\ldots,n^{\mathcal{O}(1)}\\}$ of size $\sigma$, we can
construct a data structure of size $\mathcal{O}(n\log_{\sigma}n)$ in
$\mathcal{O}(n\log_{\sigma}n)$ time, so that if query $[a,b]$ is given, we can
compute a shortest string over $\Sigma$ that does not occur in
$T[a\mathinner{.\,.}b]$ in $\mathcal{O}(1)$ time.

##  4 $\mathcal{O}(n)$ Space and $\mathcal{O}(\log\log_{\sigma}n)$ Query Time

######  Definition 1 (Order-$j$ Fragment).

Given a string $T$ over an alphabet of size $\sigma$ and an integer $j$, $V$
is called an _order- $j$ fragment_ of $T$ if and only if $V$ is a fragment of
$T$ and $S_{V}(j)=\sigma^{j}$. $V$ is further called a _minimal order- $j$
fragment_ of $T$ if $S_{U}(j)<\sigma^{j}$ and $S_{Z}(j)<\sigma^{j}$ for
$U=V[1\mathinner{.\,.}|V|-1]$ and $Z=V[2\mathinner{.\,.}|V|]$.

In particular, minimal order-$j$ fragments are pairwise not included in each
other. The following fact follows directly.

######  Fact 7.

Given a string $T$ of length $n$ over an alphabet of size $\sigma$ and an
integer $j$ we have $\mathcal{O}(n)$ minimal order-$j$ fragments. Moreover, an
arbitrary fragment $F$ of $T$ has $S_{F}[j]=\sigma^{j}$ if and only if it
contains at least one of these minimal fragments.

For each $j\in[1,\log_{\sigma}n]$, we consider all minimal order-$j$ fragments
$T$, separately. We encode the minimal order-$j$ fragments of $T$ using two
bit vectors $\textsf{SP}_{j}$ and $\textsf{EP}_{j}$, standing for starting
positions and ending positions. Inspect the following example.

######  Example 5.

We consider $T$ from Example 1 and $j=2$.

$i$ | 1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 |  10 |  11 |  12 |  13 |  14 |  15 |  16 |  17 |  18 |  19 |  20 |  21
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$T$ | a |  b |  a |  a |  b |  a |  a |  a |  b |  b |  a |  b |  b |  b |  a |  a |  a |  b |  |  |
$\textsf{APP}_{2}$ | 2 |  3 |  1 |  2 |  3 |  1 |  1 |  2 |  4 |  3 |  2 |  4 |  4 |  3 |  1 |  1 |  2 |  1 |  2 |  3 |  4
$\textsf{PRE}_{2}$ | 0 |  0 |  0 |  1 |  2 |  3 |  6 |  4 |  0 |  5 |  8 |  9 |  12 |  10 |  7 |  15 |  11 |  16 |  17 |  14 |  13
$\textsf{SP}_{2}$ | 0 |  0 |  0 |  0 |  1 |  0 |  1 |  0 |  0 |  0 |  1 |  0 |  1 |  0 |  0 |  0 |  0 |  0 |  |  |
$\textsf{EP}_{2}$ | 0 |  0 |  0 |  0 |  0 |  0 |  0 |  0 |  0 |  1 |  1 |  0 |  0 |  0 |  0 |  1 |  0 |  1 |  |  |

For instance, $\textsf{SP}_{2}[13]=1$ and $\textsf{EP}_{2}[18]=1$ denote the
minimal order-$2$ fragment $V=T[13\mathinner{.\,.}18]=\texttt{bbaaab}$.

We construct a rank and select data structure on $\textsf{SP}_{j}$ and
$\textsf{EP}_{j}$, for all $j\in[1,\ell-1]$ supporting $\mathcal{O}(1)$-time
queries. The overall space is $\mathcal{O}(n)$ by Theorem 2 and Fact 5.

Let us now explain how this data structure enables fast computation of absent
words of length $j$. Given a range $[a,b]$, by Fact 7, we only need to find
whether $T[a\mathinner{.\,.}b]$ contains a minimal order-$j$ fragment. We can
do this in $\mathcal{O}(1)$ time using one rank and one select query:
$t=\textsf{rank}_{1}(a-1,\textsf{SP}_{j})+1$ and
$\textsf{select}_{1}(t,\textsf{EP}_{j})$. The select query returns the ending
position of the leftmost minimal order-$j$ fragment that starts after the
position $a-1$; it remains to check whether this minimal order-$j$ fragment is
inside $[a,b]$.

######  Example 6.

We consider $T$, $\textsf{SP}_{2}$ and $\textsf{EP}_{2}$ from Example 5. Let
$[a,b]=[5,14]$. We have
$t=\textsf{rank}_{1}(a-1,\textsf{SP}_{2})+1=\textsf{rank}_{1}(4,\textsf{SP}_{2})+1=1$,
$\textsf{select}_{1}(t,\textsf{SP}_{2})=\textsf{select}_{1}(1,\textsf{SP}_{2})=5<b=14$
and
$\textsf{select}_{1}(t,\textsf{EP}_{2})=\textsf{select}_{1}(1,\textsf{EP}_{2})=10<b=14$,
which means $T[5,14]$ contains a minimal order-$2$ fragment.

Let us now describe a time-efficient construction of $\textsf{SP}_{j}$ and
$\textsf{EP}_{j}$. We use arrays $\textsf{PRE}_{j}$ and $\textsf{APP}_{j}$ of
$T$, which are constructible in $\mathcal{O}(n)$ time (see Section 3). Recall
that $\textsf{PRE}_{j}[i]$ stores the position of the rightmost occurrence of
rank $\textsf{APP}_{j}[i]$ in $\textsf{APP}_{j}[1\mathinner{.\,.}i-1]$ (or $0$
if such an occurrence does not exist). We apply Fact 6 as follows. We start
with all bits of $\textsf{SP}_{j}$ and $\textsf{EP}_{j}$ unset. Then, for each
$b\in[1,n]$ for which
$\textsf{PRE}_{j}[b-j+1]<\min\\{\textsf{PRE}_{j}[i]:i\in[b-j+2,|\textsf{PRE}_{j}|]\\}=a$,
we set the $b$th bit of $\textsf{EP}_{j}$ and the $a$th bit of
$\textsf{SP}_{j}$. This can be done online in a right-to-left scan of
$\textsf{PRE}_{j}$ in $\mathcal{O}(n)$ time.

######  Example 7.

We consider $T$, $\textsf{SP}_{2}$ and $\textsf{EP}_{2}$ from Example 5. We
start by setting $b=n=18$ and scan $\textsf{PRE}_{2}$ from right to left: we
have $a=13$ because $\min\\{\textsf{PRE}_{2}[i]:i\in[18,21]\\}=13$. This gives
fragment $T[13\mathinner{.\,.}18]$, which is minimal since
$\textsf{PRE}_{2}[b-1]=\textsf{PRE}_{2}[17]<13$. Then we set $b=n-1=17$ and
have $a=11$ because $\min\\{\textsf{PRE}_{2}[i]:i\in[17,21]\\}=11$. This gives
fragment $T[11\mathinner{.\,.}17]$, which is not minimal since
$\textsf{PRE}_{2}[b-1]=\textsf{PRE}_{2}[16]\geq 11$. Then we set $b=n-2=16$
and have $a=11$ because $\min\\{\textsf{PRE}_{2}[i]:i\in[16,21]\\}=11$. This
gives fragment $T[11\mathinner{.\,.}16]$, which is minimal since
$\textsf{PRE}_{2}[b-1]=\textsf{PRE}_{2}[15]<11$ .

######  Lemma 1.

$\textsf{SP}_{j}$ and $\textsf{EP}_{j}$ can be constructed in $\mathcal{O}(n)$
time.

For all $j$, the construction time is
$\mathcal{O}(n\ell)=\mathcal{O}(n\log_{\sigma}n)$ by Theorem 2, Lemma 1, and
Fact 5. All the arrays $\textsf{SP}_{j}$ and $\textsf{EP}_{j}$ in total occupy
$\mathcal{O}(n\ell)=\mathcal{O}(n\log_{\sigma}n)$ _bits_ of space, which is
$\mathcal{O}(n)$ space when measured in $\Theta(\log n)$-bit machine words. We
obtain the following lemma.

######  Lemma 2.

Given a string $T$ of length $n$ over an alphabet
$\Sigma\subset\\{1,2,\ldots,n^{\mathcal{O}(1)}\\}$ of size $\sigma$, we can
construct a data structure of size $\mathcal{O}(n)$ in
$\mathcal{O}(n\log_{\sigma}n)$ time, so that if query $(j,[a,b])$ is given, we
can check in $\mathcal{O}(1)$ time whether there is any string in $\Sigma^{j}$
that does not occur in $T[a\mathinner{.\,.}b]$, and if so return such a
string.

We can now perform binary search on $j$ using Lemma 2 to find the smallest $j$
for which $S_{T[a\mathinner{.\,.}b]}(j)<\sigma^{j}$. This results in
$\mathcal{O}(\log\ell)=\mathcal{O}(\log\log_{\sigma}n)$ query time by Fact 5.
It should now be clear that when we find the $j$ corresponding to the length
of a shortest absent word, we can output the length-$j$ suffix of the leftmost
minimal order-$j$ fragment starting after $a$. Note that outputting this
suffix is correct by the definition of minimal order-$j$ fragments.

######  Example 8.

We consider $T$, $\textsf{SP}_{2}$ and $\textsf{EP}_{2}$ from Example 5. Let
$[a,b]=[2,7]$. The length of a shortest absent word of $T[2\mathinner{.\,.}7]$
is $2$. We output bb, which is the length-$2$ suffix of the leftmost minimal
order-$2$ fragment $T[5\mathinner{.\,.}10]=\texttt{baaabb}$ starting after
$a=2$.

We obtain the following result.

######  Proposition 4.

Given a string $T$ of length $n$ over an alphabet
$\Sigma\subset\\{1,2,\ldots,n^{\mathcal{O}(1)}\\}$ of size $\sigma$, we can
construct a data structure of size $\mathcal{O}(n)$ in
$\mathcal{O}(n\log_{\sigma}n)$ time, so that if query $[a,b]$ is given, we can
compute a shortest string over $\Sigma$ that does not occur in
$T[a\mathinner{.\,.}b]$ in $\mathcal{O}(\log\log_{\sigma}n)$ time.

##  5 Combinatorial Insights

A positive integer $p$ is a _period_ of a string $S$ if $S[i]=S[i+p]$ for all
$i\in[1,|S|-p]$. We refer to the smallest period as _the period_ of the
string. Let us state the periodicity lemma, one of the most elegant
combinatorial results on strings.

######  Lemma 3 (Periodicity Lemma (weak version) [30]).

If a string $S$ has periods $p$ and $q$ such that $p+q\leq|S|$, then
$\textsf{gcd}(p,q)$ is also a period of $S$.

######  Lemma 4.

If all strings in $\\{UW:U\in\Sigma^{k}\\}$ for $W\neq\varepsilon$ occur in
some string $S$, then $|S|\geq|W|\cdot\sigma^{k}/4$.

###### Proof.

Let $p$ be the period of $W$, and let $a\in\Sigma$ be such that the period of
$aW$ is also $p$. All strings $ZbW$ for a letter $b\neq a$ and
$Z\in\Sigma^{k-1}$ must occur in $S$. Let
$A=\\{UW:U\in\Sigma^{k}\\}\setminus\\{ZaW:Z\in\Sigma^{k-1}\\}$, and note that
it is of size $\sigma^{k}-\sigma^{k-1}\geq\sigma^{k}/2$. The following claim
immediately implies the statement of the lemma.

######  Claim.

Let $i$ and $j$ be starting positions of occurrences of different strings
$UW,VW\in A$ in $S$, respectively. Then, we have $|j-i|\geq|W|/2$.

###### Proof.

Let us assume, without loss of generality, that $j>i$. Further, let us assume
towards a contradiction that $j-i<|W|/2$. Then, $j-i$ is a period of $W$ and
$p+j-i\leq|W|$ since $p\leq j-i$. Therefore, due to the periodicity lemma
(Lemma 3), $j-i$ must be divisible by the period $p$ of $W$. Hence, $V$ ends
with the letter $a$ and $VW\notin A$, a contradiction. ∎

This concludes the proof of this lemma. ∎

######  Lemma 5.

If a shortest absent word of a string $X$ is of length $\lambda$, then the
length of a shortest absent word of $XY$ is in
$[\lambda,\lambda+\max\\{10,4+\log_{\sigma}(|Y|/\lambda)\\}]$.

###### Proof.

Let $W$ and $W^{\prime}$ be shortest absent words of $X$ and $XY$,
respectively. Further, let $d=|W^{\prime}|-|W|$. In order to have $d>0$, all
strings $UW$ for $U\in\Sigma^{d-1}$ must occur in $XY$, and hence in
$X[|X|-|UW|+2\mathinner{.\,.}|X|]\cdot Y$, since none of them occurs in $X$.
Lemma 4 implies that $|Y|+\lambda+d>\lambda\cdot\sigma^{d-1}/4$. Then, since
$\lambda+d\leq 2\lambda d$ for any positive integers $\lambda,d$, we have
$|Y|>\lambda\cdot(\sigma^{d-1}/4-2d)$. Assuming that $d\geq 10$, and since
$\sigma\geq 2$, we conclude that $|Y|>\lambda\cdot\sigma^{d-1}/8$.
Consequently, $\log_{\sigma}(8|Y|/\lambda)+1>d$. Since $\log_{\sigma}8\leq 3$
we get the claimed bound. ∎

######  Lemma 6.

If a shortest absent word of $XY$ is of length $m$, a shortest absent word of
$X$ is of length $\lambda$, and $|Y|\leq m\cdot\tau$, for a positive integer
$\tau\geq 16$, then $m-\lambda\leq 10+2\log_{\sigma}\tau$.

###### Proof.

From Lemma 5 we have
$\lambda\in[m-\max\\{10,4+\log_{\sigma}(|Y|/\lambda)\\},m]$. If
$\max\\{10,4+\log_{\sigma}(|Y|/\lambda)\\}=10$, then $m-\lambda\leq 10$ and we
are done.

In the complementary case, since $|Y|\leq m\cdot\tau$, we get the following:

$\lambda\geq m-\log_{\sigma}(m\cdot\tau/\lambda)-4\iff\lambda\geq
m+\log_{\sigma}\lambda-\log_{\sigma}m-\log_{\sigma}\tau-4.$

In particular, $\lambda\geq m-\log_{\sigma}m-\log_{\sigma}\tau-4$.

From the above, if $m\leq\tau$, then $m-\lambda\leq 4+2\log_{\sigma}\tau$.

In what follows we assume that $m>\tau\geq 16$. Rearranging the original
equation, and since $\log_{\sigma}(\cdot)$ is an increasing function and
$\lambda\geq m-\log_{\sigma}m-\log_{\sigma}\tau-4$, we have

$m-\lambda\leq 4+\log_{\sigma}(m\cdot\tau/\lambda)\leq
4+\log_{\sigma}\left(\frac{m}{m-\log_{\sigma}m-\log_{\sigma}\tau-4}\right)+\log_{\sigma}\tau\\\
\leq
4+\log_{\sigma}\left(\frac{m}{m-2\log_{\sigma}m-4}\right)+\log_{\sigma}\tau.$

Then, we have $m-2\log_{\sigma}m-4\geq m/5$ since, for any $\sigma\geq 2$,
$4x/5-2\log_{\sigma}x-4$ is an increasing function on $[16,\infty)$ and
positive for $x=16$. Hence, $m-\lambda\leq
4+\log_{\sigma}5+\log_{\sigma}\tau\leq 7+\log_{\sigma}\tau$.

By combining the bounds on $m-\lambda$ we get the claimed bound. ∎

##  6 $\mathcal{O}(n)$ Space and $\mathcal{O}(1)$ Query Time

Our linear-space solution of the ISAW problem with constant query time is an
optimization of the $\mathcal{O}(n\log_{\sigma}n)$-space solution from Section
3 with some “boundary” cases processed using the data structure of Section 4.
Let us first describe a simpler $\mathcal{O}(n\log_{\sigma}\log n)$-space data
structure, which will be then optimized using the combinatorial insights from
Section 5.

Recall that we denote by $\ell$ the length of a shortest absent word of $T$.
The issue with the solution of Section 3 is that the 2d array
$\textsf{FTR}[1\mathinner{.\,.}\ell-1][1\mathinner{.\,.}n]$, equipped with
fusion trees, occupies $\mathcal{O}(n\log_{\sigma}n)$ space. In order to
reduce the memory consumption, we store the array FTR implicitly, computing
its entries on demand, and utilize succinct fusion trees from Theorem 4
instead of usual fusion trees.

Recall that $\textsf{FTR}[j][i]$ is the rightmost index of $T$ such that
$T[\textsf{FTR}[j][i]\mathinner{.\,.}i]$ contains as substrings all strings of
length $j$ over $\Sigma$ and it is equal to
$\min\\{\textsf{PRE}_{j}[i-j+2],\ldots,\textsf{PRE}_{j}[|\textsf{PRE}_{j}|]\\}$.
Therefore, the content of the 2d array FTR can be “emulated” without storing
it explicitly if one can compute in $\mathcal{O}(1)$ time the minima
$\min\\{\textsf{PRE}_{j}[a],\ldots,\textsf{PRE}_{j}[|\textsf{PRE}_{j}|]\\}$,
for any $a\in[1,n]$. For $j\in[1,\ell-1]$ and $a\in[1,n]$, denote
$M_{j,a}=\min\\{\textsf{PRE}_{j}[a],\ldots,\textsf{PRE}_{j}[|\textsf{PRE}_{j}|]\\}$.
Let us fix some $j$. Since the sequence $M_{j,1},M_{j,2},\ldots,M_{j,n}$ is
non-decreasing, we can encode it in a $2n$-bit array $B_{j}$ using the select
data structure from Theorem 2 as follows: we construct $B_{j}$ (initially
empty) by considering $a=1,2,\ldots,n$ in increasing order and, for each $a$,
we append to the end of $B_{j}$ exactly $M_{j,a}-M_{j,a-1}$ zeroes followed by
1, setting $M_{j,0}=0$ (i.e., we append the number $M_{j,a}-M_{j,a-1}$ written
in unary); then, we have $M_{j,a}=\textsf{select}_{1}(a,B_{j})-a$.

######  Example 9.

We consider $T$ from Example 1 and $j=2$.

$i$ | 1 |  2 |  3 |  4 |  5 |  6 |  7 |  8 |  9 |  10 |  11 |  12 |  13 |  14 |  15 |  16 |  17 |  18 |  19 |  20 |  21
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
$T$ | a |  b |  a |  a |  b |  a |  a |  a |  b |  b |  a |  b |  b |  b |  a |  a |  a |  b |  |  |
$\textsf{APP}_{2}$ | 2 |  3 |  1 |  2 |  3 |  1 |  1 |  2 |  4 |  3 |  2 |  4 |  4 |  3 |  1 |  1 |  2 |  1 |  2 |  3 |  4
$\textsf{PRE}_{2}$ | 0 |  0 |  0 |  1 |  2 |  3 |  6 |  4 |  0 |  5 |  8 |  9 |  12 |  10 |  7 |  15 |  11 |  16 |  17 |  14 |  13
$M_{2,i}$ | 0 |  0 |  0 |  0 |  0 |  0 |  0 |  0 |  0 |  5 |  7 |  7 |  7 |  7 |  7 |  11 |  11 |  13 |  |  |

In this case, we have $B_{2}=\tt 1\tt 1\tt 1\tt 1\tt 1\tt 1\tt 1\tt 1\tt 1\tt
0\tt 0\tt 0\tt 0\tt 0\tt 1\tt 0\tt 0\tt 1\tt 1\tt 1\tt 1\tt 1\tt 0\tt 0\tt
0\tt 0\tt 1\tt 1\tt 0\tt 0\tt 1$.

Besides access to the 2d array FTR, the algorithm of Section 3 also required
access to the values
$\operatorname*{arg\,min}\\{\textsf{PRE}_{j}[a],\ldots,\textsf{PRE}_{j}[|\textsf{PRE}_{j}|]\\}$
in order to retrieve a witness shortest absent word. To this end, we build the
$2n$-bit RMQ data structure from Theorem 1 on each array $\textsf{PRE}_{j}$;
the data structure does not need to store the array $\textsf{PRE}_{j}$ itself
to compute $\operatorname*{arg\,min}$. The arrays $B_{j}$, for
$j\in[1,\ell-1]$, equipped with select data structures, and the RMQ data
structures on arrays $\textsf{PRE}_{j}$, for $j\in[1,\ell-1]$, can be
constructed in total $\mathcal{O}(n\ell)=\mathcal{O}(n\log_{\sigma}n)$ time
and they altogether occupy $\mathcal{O}(n\log_{\sigma}n)$ _bits_ of space,
which is $\mathcal{O}(n)$ space when measured in machine words.

To answer a query $[a,b]$, it suffices to find the smallest $j$ such that
$\textsf{FTR}[j][b]<a$. We do this by finding where the predecessor of $a$
lies in $\textsf{FTR}[1\mathinner{.\,.}\ell-1][b]$. To this end, we
constructed $n$ fusion trees: one per
$\textsf{FTR}[1\mathinner{.\,.}\ell-1][i]$, resulting in a data structure of
size $\Theta(n\ell)=\mathcal{O}(n\log_{\sigma}n)$ with $\mathcal{O}(1)$ query
time. But now we do not store the arrays
$\textsf{FTR}[1\mathinner{.\,.}\ell-1][i]$ explicitly, while still having
$\mathcal{O}(1)$-time “oracle” access to their entries on demand. Hence, we
can construct a succinct fusion tree of Theorem 4, for each array
$\textsf{FTR}[1\mathinner{.\,.}\ell-1][i]$, which takes
$\mathcal{O}(\ell\log\log n)$ _bits_ of space since the size of machine words
is $w=\Theta(\log n)$ bits (a shared table mentioned in Theorem 4 is also
precomputed for all the trees in $o(2^{w})=o(n)$ time).

Thus, all the succinct fusion trees can be constructed in
$\mathcal{O}(n\log_{\sigma}n)$ time and occupy
$\mathcal{O}(n\log_{\sigma}n\log\log n)$ _bits_ , which is
$\mathcal{O}(n\log_{\sigma}\log n)$ space when measured in $\Theta(\log
n)$-bit machine words. The ISAW queries are answered in $\mathcal{O}(1)$ time
by the same algorithm as in Section 3.

Now we are to further reduce the memory usage of the data structure. We
truncate all the arrays $\textsf{FTR}[0\mathinner{.\,.}\ell-1][i]$ except
those where $i$ is a multiple of $\lfloor\log\log n\rfloor$ or $i=n$: namely,
if $i$ is a multiple of $\lfloor\log\log n\rfloor$ or $i=n$, then the succinct
fusion tree for the whole array $\textsf{FTR}[1\mathinner{.\,.}\ell-1][i]$ is
stored, occupying $\mathcal{O}(\ell\log\log n)$ bits, by Theorem 4; otherwise
($i\neq n$ is not a multiple of $\lfloor\log\log n\rfloor$), we store the
succinct fusion tree only for the subarray
$\textsf{FTR}[1\mathinner{.\,.}\lceil\log n/\log\log n\rceil][i]$, thus taking
$\mathcal{O}(\log n)$ bits, by Theorem 4. In total, the space used is
$\mathcal{O}(\frac{n}{\log\log n}\ell\log\log n+n\log n)=\mathcal{O}(n\log n)$
in bits or $\mathcal{O}(n)$ in words.

In order to answer an ISAW query for $T[a\mathinner{.\,.}b]$, we first check
whether the length $\lambda$ of a shortest absent word in
$T[a\mathinner{.\,.}b]$ is smaller than $\log n/\log\log n$ by querying the
fusion tree of $\textsf{FTR}[1\mathinner{.\,.}\lceil\log n/\log\log
n\rceil][b]$. If it is the case, then we have computed the length $\lambda$
and we find the absent word itself using RMQs exactly as in the
$\mathcal{O}(n\log_{\sigma}\log n)$-space solution described above.

Suppose that $\lambda\geq\log n/\log\log n$. We compute $b^{\prime}$, the
successor of $b$ among the positions $i$ for which we have not truncated
$\textsf{FTR}[1\mathinner{.\,.}\ell-1][i]$: $b^{\prime}=\min\\{n,\lceil
b/\lfloor\log\log n\rfloor\rceil\cdot\lfloor\log\log n\rfloor\\}$. Observe
that $[a,b]\subseteq[a,b^{\prime}]$. Then, using the fusion tree of
$\textsf{FTR}[1\mathinner{.\,.}\ell-1][b^{\prime}]$, we compute the smallest
$m$ such that $\textsf{FTR}[m][b^{\prime}]<a$. Then, $m$ is the length of a
shortest absent word in $T[a\mathinner{.\,.}b^{\prime}]$. Denote
$X=T[a\mathinner{.\,.}b]$ and $T[a\mathinner{.\,.}b^{\prime}]=XY$ where $Y$ is
a suffix of $T[a\mathinner{.\,.}b^{\prime}]$ of length $b^{\prime}-b$. We
obviously have $\lambda\leq m$. Since $|Y|=b^{\prime}-b<\log\log n$ and
$m\geq\log n/\log\log n$, we have $|Y|<m$. It follows from Lemma 6 that the
answer $\lambda$ is within a range of length $18$ from $m$. Therefore,
$\lambda$ belongs to the range $[m-18,m]$ and we can find it in
$\mathcal{O}(1)$ time using $\mathcal{O}(1)$ queries of the
$\mathcal{O}(n)$-space data structure encapsulated by Lemma 2. We thus arrive
at the main result of the paper.

*

##  7 Open Problems

It remains open whether a data structure for the ISAW problem with the same
query time and space complexities as the one encapsulated in Theorem 1 can be
constructed in linear time. Also, it is natural to pose the following related
open problem, which may require the development of fundamentally different
techniques. Given a string $T$ of length $n$ over an alphabet
$\Sigma\subset\\{1,2,\ldots,n^{\mathcal{O}(1)}\\}$, preprocess $T$ so that
given a range $[i,j]$, we can return a representation of a shortest string
over $\Sigma_{[i,j]}$ that is absent in the fragment $T[i]\cdots T[j]$ of $T$,
where $\Sigma_{[i,j]}$ is the set of letters from $\Sigma$ occurring in the
fragment $T[i]\cdots T[j]$.

## References

  * Abedin et al. [2018] Abedin, P., Ganguly, A., Hon, W., Nekrich, Y., Sadakane, K., Shah, R., Thankachan, S.V., 2018.  A linear-space data structure for Range-LCP queries in poly-logarithmic time, in: Computing and Combinatorics - 24th International Conference, COCOON 2018, pp. 615–625.  URL: https://doi.org/10.1007/978-3-319-94776-1_51, doi:10.1007/978-3-319-94776-1\\_51.
  * Abedin et al. [2020] Abedin, P., Ganguly, A., Pissis, S.P., Thankachan, S.V., 2020\.  Efficient data structures for range shortest unique substring queries.  Algorithms 13, 276\.  URL: https://doi.org/10.3390/a13110276, doi:10.3390/a13110276.
  * Amir et al. [2014] Amir, A., Apostolico, A., Landau, G.M., Levy, A., Lewenstein, M., Porat, E., 2014\.  Range LCP.  J. Comput. Syst. Sci. 80, 1245–1253.  URL: https://doi.org/10.1016/j.jcss.2014.02.010, doi:10.1016/j.jcss.2014.02.010.
  * Amir et al. [2020] Amir, A., Charalampopoulos, P., Pissis, S.P., Radoszewski, J., 2020\.  Dynamic and internal longest common substring.  Algorithmica 82, 3707–3743.  URL: https://doi.org/10.1007/s00453-020-00744-0, doi:10.1007/s00453-020-00744-0.
  * Ayad et al. [2019] Ayad, L.A.K., Badkobeh, G., Fici, G., Héliou, A., Pissis, S.P., 2019.  Constructing antidictionaries in output-sensitive space, in: Data Compression Conference, DCC 2019, IEEE. pp. 538–547.  URL: https://doi.org/10.1109/DCC.2019.00062, doi:10.1109/DCC.2019.00062.
  * Babenko et al. [2016] Babenko, M.A., Gawrychowski, P., Kociumaka, T., Kolesnichenko, I.I., Starikovskaya, T., 2016.  Computing minimal and maximal suffixes of a substring.  Theor. Comput. Sci. 638, 112–121.  URL: https://doi.org/10.1016/j.tcs.2015.08.023, doi:10.1016/j.tcs.2015.08.023.
  * Babenko et al. [2015] Babenko, M.A., Gawrychowski, P., Kociumaka, T., Starikovskaya, T., 2015\.  Wavelet trees meet suffix trees, in: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, SIAM. pp. 572–591.  URL: https://doi.org/10.1137/1.9781611973730.39, doi:10.1137/1.9781611973730.39.
  * Badkobeh et al. [2021] Badkobeh, G., Charalampopoulos, P., Pissis, S.P., 2021.  Internal shortest absent word queries, in: Gawrychowski, P., Starikovskaya, T. (Eds.), 32nd Annual Symposium on Combinatorial Pattern Matching, CPM 2021, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany. pp. 24:1–24:18.
  * Barton et al. [2014] Barton, C., Héliou, A., Mouchard, L., Pissis, S.P., 2014\.  Linear-time computation of minimal absent words using suffix array.  BMC Bioinform. 15, 388\.  URL: https://doi.org/10.1186/s12859-014-0388-9, doi:10.1186/s12859-014-0388-9.
  * Barton et al. [2015] Barton, C., Héliou, A., Mouchard, L., Pissis, S.P., 2015\.  Parallelising the computation of minimal absent words, in: Parallel Processing and Applied Mathematics - 11th International Conference, PPAM 2015. Revised Selected Papers, Part II, Springer. pp. 243–253.  URL: https://doi.org/10.1007/978-3-319-32152-3_23, doi:10.1007/978-3-319-32152-3\\_23.
  * Bender and Farach-Colton [2000] Bender, M.A., Farach-Colton, M., 2000\.  The LCA problem revisited, in: LATIN 2000: Theoretical Informatics, 4th Latin American Symposium, Proceedings, Springer. pp. 88–94.  URL: https://doi.org/10.1007/10719839_9, doi:10.1007/10719839\\_9.
  * Berkman and Vishkin [1993] Berkman, O., Vishkin, U., 1993\.  Recursive star-tree parallel data structure.  SIAM J. Comput. 22, 221–242.  URL: https://doi.org/10.1137/0222017, doi:10.1137/0222017.
  * Birenzwige et al. [2020] Birenzwige, O., Golan, S., Porat, E., 2020.  Locally consistent parsing for text indexing in small space, in: Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, SIAM. pp. 607–626.  URL: https://doi.org/10.1137/1.9781611975994.37, doi:10.1137/1.9781611975994.37.
  * Chairungsee and Crochemore [2012] Chairungsee, S., Crochemore, M., 2012\.  Using minimal absent words to build phylogeny.  Theor. Comput. Sci. 450, 109–116.  URL: https://doi.org/10.1016/j.tcs.2012.04.031, doi:10.1016/j.tcs.2012.04.031.
  * Chan et al. [2011] Chan, T.M., Larsen, K.G., Pătraşcu, M., 2011.  Orthogonal range searching on the ram, revisited, in: Hurtado, F., van Kreveld, M.J. (Eds.), Proceedings of the 27th ACM Symposium on Computational Geometry, Paris, France, June 13-15, 2011, ACM. pp. 1–10.  URL: https://doi.org/10.1145/1998196.1998198, doi:10.1145/1998196.1998198.
  * Charalampopoulos et al. [2018a] Charalampopoulos, P., Crochemore, M., Fici, G., Mercaş, R., Pissis, S.P., 2018a.  Alignment-free sequence comparison using absent words.  Inf. Comput. 262, 57–68.  URL: https://doi.org/10.1016/j.ic.2018.06.002, doi:10.1016/j.ic.2018.06.002.
  * Charalampopoulos et al. [2018b] Charalampopoulos, P., Crochemore, M., Pissis, S.P., 2018b.  On extended special factors of a word, in: String Processing and Information Retrieval - 25th International Symposium, SPIRE 2018, Springer. pp. 131–138.  URL: https://doi.org/10.1007/978-3-030-00479-8_11, doi:10.1007/978-3-030-00479-8\\_11.
  * Charalampopoulos et al. [2021] Charalampopoulos, P., Gawrychowski, P., Mozes, S., Weimann, O., 2021\.  An almost optimal edit distance oracle.  CoRR abs/2103.03294.  arXiv:2103.03294.
  * Charalampopoulos et al. [2020a] Charalampopoulos, P., Kociumaka, T., Mohamed, M., Radoszewski, J., Rytter, W., Straszynski, J., Walen, T., Zuba, W., 2020a.  Counting distinct patterns in internal dictionary matching, in: 31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020, Schloss Dagstuhl - Leibniz-Zentrum für Informatik. pp. 8:1–8:15.  URL: https://doi.org/10.4230/LIPIcs.CPM.2020.8, doi:10.4230/LIPIcs.CPM.2020.8.
  * Charalampopoulos et al. [2019] Charalampopoulos, P., Kociumaka, T., Mohamed, M., Radoszewski, J., Rytter, W., Walen, T., 2019\.  Internal dictionary matching, in: 30th International Symposium on Algorithms and Computation, ISAAC 2019, Schloss Dagstuhl - Leibniz-Zentrum für Informatik. pp. 22:1–22:17.  URL: https://doi.org/10.4230/LIPIcs.ISAAC.2019.22, doi:10.4230/LIPIcs.ISAAC.2019.22.
  * Charalampopoulos et al. [2020b] Charalampopoulos, P., Kociumaka, T., Wellnitz, P., 2020b.  Faster approximate pattern matching: A unified approach, in: 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, IEEE. pp. 978–989.  URL: https://doi.org/10.1109/FOCS46700.2020.00095, doi:10.1109/FOCS46700.2020.00095.
  * Crochemore et al. [2020] Crochemore, M., Héliou, A., Kucherov, G., Mouchard, L., Pissis, S.P., Ramusat, Y., 2020\.  Absent words in a sliding window with applications.  Inf. Comput. 270.  doi:10.1016/j.ic.2019.104461.
  * Crochemore et al. [1998] Crochemore, M., Mignosi, F., Restivo, A., 1998.  Automata and forbidden words.  Inf. Process. Lett. 67, 111–117.  doi:10.1016/S0020-0190(98)00104-5.
  * Crochemore et al. [2000] Crochemore, M., Mignosi, F., Restivo, A., Salemi, S., 2000\.  Data compression using antidictionaries.  Proceedings of the IEEE 88, 1756–1768.  doi:10.1109/5.892711.
  * Farach [1997] Farach, M., 1997.  Optimal suffix tree construction with large alphabets, in: 38th Annual Symposium on Foundations of Computer Science, FOCS 1997, IEEE Computer Society. pp. 137–143.  URL: https://doi.org/10.1109/SFCS.1997.646102, doi:10.1109/SFCS.1997.646102.
  * Ferenczi [1999] Ferenczi, S., 1999.  Complexity of sequences and dynamical systems.  Discret. Math. 206, 145–154.  URL: https://doi.org/10.1016/S0012-365X(98)00400-2, doi:10.1016/S0012-365X(98)00400-2.
  * Fici and Gawrychowski [2019] Fici, G., Gawrychowski, P., 2019\.  Minimal absent words in rooted and unrooted trees, in: String Processing and Information Retrieval - 26th International Symposium, SPIRE 2019, Springer. pp. 152–161.  doi:10.1007/978-3-030-32686-9\\_11.
  * Fici et al. [2006] Fici, G., Mignosi, F., Restivo, A., Sciortino, M., 2006\.  Word assembly through minimal forbidden words.  Theor. Comput. Sci. 359, 214–230.  doi:10.1016/j.tcs.2006.03.006.
  * Fici et al. [2019] Fici, G., Restivo, A., Rizzo, L., 2019.  Minimal forbidden factors of circular words.  Theor. Comput. Sci. 792, 144–153.  URL: https://doi.org/10.1016/j.tcs.2018.05.037, doi:10.1016/j.tcs.2018.05.037.
  * Fine and Wilf [1965] Fine, N.J., Wilf, H.S., 1965\.  Uniqueness theorems for periodic functions.  Proceedings of the American Mathematical Society 16, 109–114.  URL: http://www.jstor.org/stable/2034009.
  * Fischer and Heun [2011] Fischer, J., Heun, V., 2011\.  Space-efficient preprocessing schemes for range minimum queries on static arrays.  SIAM J. Comput. 40, 465–492.  URL: https://doi.org/10.1137/090779759, doi:10.1137/090779759.
  * Fredman and Willard [1993] Fredman, M.L., Willard, D.E., 1993\.  Surpassing the information theoretic bound with fusion trees.  J. Comput. Syst. Sci. 47, 424–436.  doi:10.1016/0022-0000(93)90040-4.
  * Fujishige et al. [2016] Fujishige, Y., Tsujimaru, Y., Inenaga, S., Bannai, H., Takeda, M., 2016.  Computing DAWGs and minimal absent words in linear time for integer alphabets, in: 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, Schloss Dagstuhl - Leibniz-Zentrum für Informatik. pp. 38:1–38:14.  doi:10.4230/LIPIcs.MFCS.2016.38.
  * Ganguly et al. [2018] Ganguly, A., Patil, M., Shah, R., Thankachan, S.V., 2018\.  A linear space data structure for range LCP queries.  Fundam. Inform. 163, 245–251.  URL: https://doi.org/10.3233/FI-2018-1741, doi:10.3233/FI-2018-1741.
  * Garcia et al. [2011] Garcia, S.P., Pinho, A.J., Rodrigues, J.M.O.S., Bastos, C.A.C., Ferreira, P.J.S.G., 2011.  Minimal absent words in prokaryotic and eukaryotic genomes.  PLoS ONE 6.  doi:10.1371/journal.pone.0016065.
  * Grossi et al. [2009] Grossi, R., Orlandi, A., Raman, R., Rao, S.S., 2009\.  More haste, less waste: Lowering the redundancy in fully indexable dictionaries, in: Albers, S., Marion, J.Y. (Eds.), 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany. pp. 517–528.  doi:10.4230/LIPIcs.STACS.2009.1847.
  * Harel and Tarjan [1984] Harel, D., Tarjan, R.E., 1984\.  Fast algorithms for finding nearest common ancestors.  SIAM J. Comput. 13, 338–355.  URL: https://doi.org/10.1137/0213024, doi:10.1137/0213024.
  * Jacobson [1989] Jacobson, G., 1989.  Space-efficient static trees and graphs, in: 30th Annual Symposium on Foundations of Computer Science, FOCS 1989, IEEE Computer Society. pp. 549–554.  doi:10.1109/SFCS.1989.63533.
  * Keller et al. [2014] Keller, O., Kopelowitz, T., Feibish, S.L., Lewenstein, M., 2014\.  Generalized substring compression.  Theor. Comput. Sci. 525, 42–54.  URL: https://doi.org/10.1016/j.tcs.2013.10.010, doi:10.1016/j.tcs.2013.10.010.
  * Kempa and Kociumaka [2019] Kempa, D., Kociumaka, T., 2019\.  String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure, in: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, ACM. pp. 756–767.  URL: https://doi.org/10.1145/3313276.3316368, doi:10.1145/3313276.3316368.
  * Kociumaka [2016] Kociumaka, T., 2016.  Minimal suffix and rotation of a substring in optimal time, in: 27th Annual Symposium on Combinatorial Pattern Matching, CPM 2016, pp. 28:1–28:12.  URL: https://doi.org/10.4230/LIPIcs.CPM.2016.28, doi:10.4230/LIPIcs.CPM.2016.28.
  * Kociumaka [2018] Kociumaka, T., 2018.  Efficient Data Structures for Internal Queries in Texts.  Ph.D. thesis. University of Warsaw.  URL: https://mimuw.edu.pl/~kociumaka/files/phd.pdf.
  * Kociumaka et al. [2012] Kociumaka, T., Radoszewski, J., Rytter, W., Walen, T., 2012\.  Efficient data structures for the factor periodicity problem, in: String Processing and Information Retrieval \- 19th International Symposium, SPIRE 2012, pp. 284–294.  URL: https://doi.org/10.1007/978-3-642-34109-0_30, doi:10.1007/978-3-642-34109-0\\_30.
  * Kociumaka et al. [2015] Kociumaka, T., Radoszewski, J., Rytter, W., Walen, T., 2015\.  Internal pattern matching queries in a text and applications, in: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, SIAM. pp. 532–551.  URL: https://doi.org/10.1137/1.9781611973730.36, doi:10.1137/1.9781611973730.36.
  * Landau and Vishkin [1988] Landau, G.M., Vishkin, U., 1988\.  Fast string matching with k differences.  J. Comput. Syst. Sci. 37, 63–78.  URL: https://doi.org/10.1016/0022-0000(88)90045-1, doi:10.1016/0022-0000(88)90045-1.
  * Matsuda et al. [2020] Matsuda, K., Sadakane, K., Starikovskaya, T., Tateshita, M., 2020\.  Compressed orthogonal search on suffix arrays with applications to range LCP, in: 31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020, June 17-19, 2020, Copenhagen, Denmark, pp. 23:1–23:13.  URL: https://doi.org/10.4230/LIPIcs.CPM.2020.23, doi:10.4230/LIPIcs.CPM.2020.23.
  * Mieno et al. [2020] Mieno, T., Kuhara, Y., Akagi, T., Fujishige, Y., Nakashima, Y., Inenaga, S., Bannai, H., Takeda, M., 2020\.  Minimal unique substrings and minimal absent words in a sliding window, in: 46th SOFSEM, Springer. pp. 148–160.  doi:10.1007/978-3-030-38919-2\\_13.
  * Mignosi et al. [2002] Mignosi, F., Restivo, A., Sciortino, M., 2002.  Words and forbidden factors.  Theor. Comput. Sci. 273, 99–117.  doi:10.1016/S0304-3975(00)00436-9.
  * Munro et al. [2020] Munro, J.I., Navarro, G., Nekrich, Y., 2020.  Text indexing and searching in sublinear time, in: 31st Annual Symposium on Combinatorial Pattern Matching, CPM 2020, Schloss Dagstuhl - Leibniz-Zentrum für Informatik. pp. 24:1–24:15.  URL: https://doi.org/10.4230/LIPIcs.CPM.2020.24, doi:10.4230/LIPIcs.CPM.2020.24.
  * Navarro [2016] Navarro, G., 2016.  Compact Data Structures - A Practical Approach.  Cambridge University Press.
  * Ota and Morita [2010] Ota, T., Morita, H., 2010.  On the adaptive antidictionary code using minimal forbidden words with constant lengths, in: Proceedings of the International Symposium on Information Theory and its Applications, ISITA 2010, IEEE. pp. 72–77.  doi:10.1109/ISITA.2010.5649621.
  * Pǎtraşcu and Thorup [2014] Pǎtraşcu, M., Thorup, M., 2014\.  Dynamic integer sets with optimal rank, select, and predecessor search, in: 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, IEEE Computer Society. pp. 166–175.  URL: https://doi.org/10.1109/FOCS.2014.26, doi:10.1109/FOCS.2014.26.
  * Pratas and Silva [2020] Pratas, D., Silva, J.M., 2020\.  Persistent minimal sequences of SARS-CoV-2.  Bioinformatics doi:10.1093/bioinformatics/btaa686. btaa686.
  * Raskhodnikova et al. [2013] Raskhodnikova, S., Ron, D., Rubinfeld, R., Smith, A.D., 2013\.  Sublinear algorithms for approximating string compressibility.  Algorithmica 65, 685–709.  URL: https://doi.org/10.1007/s00453-012-9618-6, doi:10.1007/s00453-012-9618-6.
  * Rubinchik and Shur [2017] Rubinchik, M., Shur, A.M., 2017\.  Counting palindromes in substrings, in: String Processing and Information Retrieval - 24th International Symposium, SPIRE 2017, Springer. pp. 290–303.  URL: https://doi.org/10.1007/978-3-319-67428-5_25, doi:10.1007/978-3-319-67428-5\\_25.
  * Silva et al. [2015] Silva, R.M., Pratas, D., Castro, L., Pinho, A.J., Ferreira, P.J.S.G., 2015.  Three minimal sequences found in Ebola virus genomes and absent from human DNA.  Bioinform. 31, 2421–2425.  URL: https://doi.org/10.1093/bioinformatics/btv189, doi:10.1093/bioinformatics/btv189.
  * Tanimura et al. [2017] Tanimura, Y., Nishimoto, T., Bannai, H., Inenaga, S., Takeda, M., 2017.  Small-space LCE data structure with constant-time queries, in: 42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017, Schloss Dagstuhl - Leibniz-Zentrum für Informatik. pp. 10:1–10:15.  URL: https://doi.org/10.4230/LIPIcs.MFCS.2017.10, doi:10.4230/LIPIcs.MFCS.2017.10.
  * Tiskin [2008] Tiskin, A., 2008.  Semi-local string comparison: Algorithmic techniques and applications.  Math. Comput. Sci. 1, 571–603.  URL: https://doi.org/10.1007/s11786-007-0033-3, doi:10.1007/s11786-007-0033-3.
  * Yao [1982] Yao, A.C., 1982.  Space-time tradeoff for answering range queries (extended abstract), in: Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, ACM. pp. 128–136.  doi:10.1145/800070.802185.


# Ultimate limits of future colliders††thanks: Work supported by DOE

M.Bai<EMAIL_ADDRESS>SLAC National Accelerator Laboratory  Menlo Park
CA 94025  USA
V.Shiltsev1 Fermilab  Batavia  IL 60510  USA
F. Zimmermann 1 CERN  1211 Meyrin  Switzerland

###### Abstract

With seven operational colliders in the world and two under construction, the
international particle physics community not only actively explores options
for the next facilities for detailed studies of the Higgs/electroweak physics
and beyond-the-LHC energy frontier, but also seeks a clear picture of the
limits of the colliding beams method. In this paper, we try to consolidate
various recent efforts in identifying physics limits of colliders in
conjunction with societal sustainability, and share our thoughts about the
perspective of reaching the ultimate quantum limit.

##  1 The Landscape of colliders

The development of accelerators and beams in the past century has led to
incredible discoveries in physics, chemistry, biology, etc. Up to date, about
25 Nobel Prizes in Physics and 7 in Chemistry were made possible thanks to
significant contributions from particles accelerators and beams [1, 2]. Among
the family of accelerators, the collider has been the most important engine of
discovery for particle physicists to produce new particles and to understand
the fundamental laws that govern the subatomic structure. Figure 1 shows how
the energy of colliders has increased orders of magnitudes over the past half
a century.

Figure 1: The so-called Livingston plot represents the evolution of the
colliders from the past to the future [2].

Table 1 lists the colliders that are currently in operation and two which are
under construction (NICA in Russia and the Electron Ion Collider at BNL in the
USA).

Table 1: Operational particle colliders. Collider | Location | Species | Energy per
---|---|---|---
|  |  | beam [GeV]
LHC/ | CERN, | p | 6800
HL-LHC | Europe | Pb, Xe | 2560
RHIC | BNL, USA | p↑ | 255
|  | d, Au, etc | 100/n
SuperKEKB | KEK, Japan | e+e- | 7 e-, 4 e+
BEPCII | IHEP, China | e+e- | 2.45
DA$\Phi$NE | LNF, Italy | e+e- | 0.51
VEPP-2000 | BINP, Russia | e+e- | 1
VEPP-4M | BINP, Russia | e+e- | 6
NICA | JINR, Russia | Au, etc | 4.5/n
EIC | BNL, USA | e↑, p↑ | 18e-, 255p
|  | He3 | 167/n
|  | Au. etc | 100/n

Despite a noticeable slow-down in the increase of the energy frontier over the
past couple of decades, the quest for further pushing the collider frontier
has never abated. At the latest US High Energy Physics long term strategy
community process known as Snowmass’21, the high energy physics community has
composed its long-term energy-frontier road map, which consists of three
elements: to ensure the success of the ongoing LHC luminosity upgrade (HL-
LHC), to realize Higgs factory e+e- collider for studying the Higgs boson and
electroweak physics with a high precision, and to develop multi-TeV colliders
for probing the 10 TeV parton energy scale [3]. These requirements clearly
push the future colliders, once again, into an hitherto unprecedented scale as
shown in Fig. 2, where they may face many challenges both in terms of reaching
the advertised performance as well as for maintaining societal support [4].

Figure 2: Collider peak luminosity and size as a function of centre-of-mass
energy. The red bubbles represent the lepton colliders while the blue bubbles
are the hadron colliders. For both cases, the semi transparent bubbles are the
proposed colliders for future. The size (diameter or length) of the collider
is represented by the size of the bubble.

##  2 Ultimate limits of future energy frontier colliders

###  2.1 Energy

For circular electron-positron colliders, due to the synchrotron radiation,
the energy of the circular collider is ultimately limited by
$E_{e^{+}e^{-}}\lesssim 500{\rm GeV}(\frac{R}{10{\rm km}})^{1/3}$, where
$E_{e^{+}e^{-}}$ is the centre-of-mass energy and $R$ is the ring radius. The
beam energy of a circular hadron collider is limited both by the size $R$, and
also by the available bending magnetic field. The current proposed 100 TeV
center-of-mass energy proton proton colliders such as the FCC-hh at CERN, with
a circumference close to 100 km, requires dipole magnets of 16 Tesla or
beyond, which are currently under research and development. Larger colliders
which have been suggested include the Collider in the Sea [5] and a Circular
Collider on the Moon [6]. However, the construction and operation of the
future colliders of any type must also stay sustainable. To reach 1 PeV
centre-of-mass energy in the FCC-hh’s 91 km tunnel will require 10 times
stronger bending magnet. To go further beyond, the circular proton proton
collider will also experience a similar energy limit and size scaling as the
electron-positron circular colliders, namely $E_{pp}<10{\rm
PeV}(\frac{R}{10{\rm km}})^{1/3}$, due to synchrotron radiation.

For linear e+s- colliders, the ultimate beam energy is determined by the limit
of acceleration gradient. For CLIC with 100 MV/m acceleration gradient normal
conducting technology, a 50 km long laser straight tunnel is required to reach
3 TeV. The recent development in cryogenic copper C-band technology offers a
potential path to push the acceleration gradient towards 150 MV/m [7]. Based
on this technology, the newly proposed Cool Copper Collider [8] concept could
possibly enable a center-of-mass energy to 4.5 TeV within the same 50 km
tunnel. To obtain centre-of-mass energies of 10 TeV and beyond will require
quite a few substantial developments in

  * •

extreme high gradient RF acceleration structures;

  * •

laser straight long tunnel construction to avoid vertical emittance growth due
to bending fields otherwise required to follow the earth curvature [9]; and

  * •

cost-effective high efficient RF power sources.

The concept of colliding muons, which emit much less synchrotron radiation
then electrons, has been developed since several decades. Despite the
advantage of being less susceptible to synchrotron radiation in comparison to
electrons or positrons, the muon collider energy is ultimately limited by the
available acceleration within the lifetime of the muons [4, 9]. Depending on
the site of future multi-TeV muon collider, the neutrino flux from the muon
decay is likely to become another factor limiting the maximum energy [4, 9].

###  2.2 luminosity

In general, the luminosity of a collider, assuming symmetric collision, is
given by

$L=\frac{1}{2\pi}\frac{P_{wall}{\eta}}{E_{cm}}\frac{N_{b}}{\sigma_{x}^{*}\sigma_{y}^{*}}F_{geom}\;,$
(1)

where $P_{wall}$ denotes the wall-plug power, $\eta$ the ratio of wall-plug
power to beam power, $N_{b}$ the number of particles per bunch,
$\sigma_{x}^{*}$ and $\sigma_{y}^{*}$ the horizontal and vertical rms beam
sizes at the interaction point (IP). Finally, $F_{geom}$ describes the
geometric factors such as hour-glass, pinch effect for collisions of particles
with opposite charge state, etc.

Equation (1) shows that for a given optics at the IP, the luminosity scales
linearly with energy. On the other hand, the discovery of new fundamental
constituents with the lepton collider requires that the luminosity scales with
the square of the centre-of-mass energy $E_{cm}$ as
$\left(\frac{E_{cm}}{10TeV}\right)^{2}\times 10^{35}$ cm-2s-1 [3]. As an
example, the minimum luminosity for a direct search of new physics at a lepton
collider of 10 TeV $E_{cm}$ is $2\times 10^{31}$ cm-2s-1 and minimum
luminosity is $E_{cm}$ is $3\times 10^{34}$ cm-2s-1 for precision measurement.
However, extremely high luminosity at lower energies can also lead to
discoveries through the observation of rare processes. For example, operating
the FCC-ee as a “TeraZ” factory at 91 GeV c.m. could lead to the discovery of
sterile right-handed neutrinos.

For hadron colliders, the mass of the particle that can be created scales with
$E_{cm}^{2/3}L^{1/6}$ [10, 2, 3], and the ultimate aim, in this case, is to
reach collision at $\geq$ 100 TeV centre-of-mass energy with $10^{35}-10^{36}$
cm-2s-1 luminosity [3]. Hence, the beam brightness needs to be scaled with the
energy accordingly for future colliders. This requires one to overcome many
limiting factors starting from obtaining and preserving low emittance bright
beams through the acceleration process, final focusing as well as the impact
of beam-beam interaction to beam dynamics and detector background. Thanks to
the advancements in beam dynamics and beam techniques, such as compensation of
various beam-beam effects, crab crossing, etc, over the past decades, the
luminosity performance of current operating colliders has been impressive, as
is shown in Fig. 2. Despite their low energy and compact size, both DA$\Phi$NE
and BEPC-II were able to reach much higher peak luminosity than earlier
generations of circular colliders at the same energies. Also LEP, CESR and the
three B factories PEP-II, KEKB, SuperKEKB achieved many orders of magnitude
higher luminosity than the first generation high energy e+e- linear collider
SLC. Nevertheless, to reach similar peak luminosity performance, future multi-
TeV e+e- colliders face additional unique limiting factors due to
beamstrahlung, Oide effect, and coherent pair production. These effects have
been carefully studied and are well understood. Also various mitigation
measures have been proposed.

In principle, the ultimate achievable normalized beam emittance in each of
three dimensions for a bunch of $N_{b}$ unpolarized fermions (electrons or
positrons) is its quantum limit, i.e.
$\gamma\epsilon_{n}^{QM}={N_{b}}^{1/3}{\mkern 0.75mu\mathchar
22\relax\mkern-9.75mu\lambda}_{p}/4$, where ${\mkern 0.75mu\mathchar
22\relax\mkern-9.75mu\lambda}_{p}$ is the particle’s de Broglie wavelength
[11]. In such a scenario, without taking into account other limiting factors
such as beamstrahlung and Oide effect, the ultimately quantum-limited
luminosity is still orders of magnitude above the luminosity targets desired
for the multi-TeV e+e- colliders [9]. Nevertheless, utilization of a beam with
a quantum-limited emittance at the collision point at multi TeV energies
requires a beam delivery system able to manipulate beams of extremely small
dimensions, much below the current state of the art.

###  2.3 Advanced acceleration concept based collider

It is evident that, so far, the colliders based on conventional RF technology
have not yet reached their physical limits, neither in energy nor in
luminosity. Nevertheless, the actual physical engineering limits and societal
sustainability have been the two main limiting factors of the proposed future
high energy colliders. Figure 3 shows the power consumption of energy frontier
colliders, both currently in operation and proposed for the future [12]. For
the case of LHC, the current power consumption of LHC operation including
detectors, but without the rest of the CERN accelerator complex, is 0.6 TWh
per year, which is about 10% of what Swissgrid produces [13]. Assuming the
same running scenario, FCC could be consuming close to 50% what Swissgrid
produces.

Figure 3: Power consumption of current and proposed future energy frontier
colliders [12].

Hence, disruptive technologies for acceleration as well as for beam
manipulation, such as high temperature superconducting technologies, may be
required to find a path forward to realize the future energy frontier
colliders within the limits of societal sustainability, and to continue
pushing the energy frontier far beyond the currently proposed multi-TeV
colliders.

Both laser driven and beam driven plasma wakefield acceleration, a.k.a. LWFA
and PWFA, have been pursued and intensified worldwide. While unprecedented
acceleration gradient has been demonstrated with both PWFA and LWFA, the
achieved beam quality, both intensity and brightness, has not yet reached a
comparable level to what conventional RF technology based colliders have
routinely delivered. The recent progress of AWAKE has shown encouraging steps
towards a possibly very high energy electron-proton collider based on beam-
driven PWFA [14]. Nevertheless, the projected luminosity is on the order of
$10^{28}$ to $10^{29}$ $cm^{-2}s^{-1}$, and falls far short of the physics
requirement. Overall, the path towards next generation TeV colliders still
requires numerous new marvels in beam physics as well as in engineering to
meet the repetition rate, staging requirement and ultimately the beam
performance that conventional RF technology based accelerators have always
achieved.

Nevertheless, as the advanced concept acceleration field is rapidly
developing, it is not appropriate to estimate the performance limit at this
point of time. In addition to accelerating gradient, beam quality and energy
efficiency will be of high importance.

In addition to the LWFA and PWFA, other creative ideas such as using crystals
for accelerating and finally focusing and colliding positively charged
particles, or accelerating single particle with black hole to reach Planck
energy have been proposed [15, 16]. For a crystal channeling collider, the
estimated luminosity is [15]

$L_{c}=f_{rep}n_{ch}\frac{N_{c}^{2}\sqrt{KE}}{2\pi\hbar c}$ (2)

where, $n_{ch}$ is number of crystal channels and $N_{c}$ is the number of
particles captured in each crystal channel, $K$ is the crystal’s channeling
strength. Typical crystal $K$ is around $10^{11}$ GeV/m2. As the focusing in
the crystal accelerator is continuous, quantum emittance could be achieved
with particles remaining in the ground state. While these ideas are still at
very infant stage, the crystal channeling technique (without longitudinal
acceleration) has been successfully developed and used for collimation at LHC.

Other potentially disruptive concepts include the collision of crystalline
beams [17, 18], and harnessing quantum entanglement for acceleration or
focusing [16].

##  3 CONCLUSION

The past half a century has seen the rise of colliders that led to many
discoveries. While the pace for new colliders at the energy frontier has
slowed down, the quest for the next discovery collider still remains strong.
The realization of currently proposed future colliders, circular or linear
e+e- colliders and 100 TeV pp colliders, is likely to push the energy frontier
by another order of magnitude. Nevertheless, both in terms of energy and
luminosity, these machines are still far below the ultimate frontier set by
the quantum limit.

Hence, new paradigms for acceleration and beam manipulation are required to
overcome the barriers that seem to be formidable with currently available
technologies. A breakthrough in this domain will not only benefit the energy
frontier particle physics, but it can also be a game changer for other
accelerator based scientific fields such as those served by X-ray Free
Electron Lasers.

##  4 ACKNOWLEDGEMENTS

The authors would like to thank the co-organizers and participants of the
Physics Limit of Ultimate Beams workshop series.

## References

  * [1] E. Haussecker and A. W. Chao, The Influence of Accelerator Science on Physics Research, Phys. Perspect., 13(2) (2011): 146-160, DOI 10.1007/s00016-010-0049-y
  * [2] V.Shiltsev, F.Zimmermann, Modern and future colliders, Rev.Mod.Phys. 93(1) (2021) 015006, DOI 10.1103/RevModPhys.93.015006
  * [3] Snowmass workshop serials https://indico.fnal.gov/event/46742/
  * [4] V. Shiltsev, FERMILAB-CONF-21-257-AD-APC https://lss.fnal.gov/archive/2021/conf/fermilab-conf-21-257-ad-apc.pdf
  * [5] P.M. McIntyre et al., Proc. NAPAC16, Chicago, IL, USA MOB2CO03 (2016) p. 13
  * [6] J. Beacham and F. Zimmermann, New J. Phys. 24 023029 (2002)
  * [7] Nasr et al, Phys. Rev. Accel. Beams 24, 093201, 2021
  * [8] E. Nanni, C. Vernieri et al, https://arxiv.org/pdf/2110.15800.pdf, 2021
  * [9] F. Zimmermann et al, Proceedings of IPAC21, 2021
  * [10] L. Teng, Proc. 2nd APAC, Beijing (2001) p. 926
  * [11] F. Zimmermann, Quantum Mechanical Limits on Beam Demagnification and Luminosity, in Proc. Nanobeam’03, Lausanne, Switzerland, 2003, p. 69
  * [12] P. Lebrun, presentation at 4th Workshop Energy for Sustainable Science at Research Infrastructures, 2017
  * [13] https://home.cern/resources/faqs/facts-and-figures-about-lhc#:~:text=What%20is%20the%20LHC%20power,is%20750%20GWh%20per%20year.
  * [14] Snowmass workshop series, https://indico.fnal.gov/event/46645/
  * [15] Snowmass workshop series, https://indico.fnal.gov/event/47819/
  * [16] S. Brooks, https://arxiv.org/pdf/1811.12479.pdf
  * [17] A.F. Haffmans et al., Proc. PAC95 (1995) doi: 10.1109/PAC.1995.505871
  * [18] J. Wei, A. Sessler, Proc. EPAC98 (1998) p. 862