Department of Informatics, Kyushu University and Japan Society for Promotion
of Science (JSPS),
Japandominik.koeppl@inf.kyushu-u.ac.jphttps://orcid.org/0000-0002-8721-4444JSPS
KAKENHI Grant Number JP18F18120. Graduate School of Information Sciences,
Tohoku University<EMAIL_ADDRESS>Graduate
School of Information Sciences, Tohoku University,
Japandiptarama@tohoku.ac.jphttps://orcid.org/0000-0002-8168-7312JSPS KAKENHI
Grant Number JP19K20208. Graduate School of Information Sciences, Tohoku
University, Japanayumis@tohoku.ac.jphttps://orcid.org/0000-0002-4978-8316JSPS
KAKENHI Grant Number JP15H05706. Dominik Köppl, Daiki Hashimoto, Diptarama
Hendrian, and Ayumi Shinohara [100]Theory of computation [500]Mathematics of
computing Combinatorics on words 10.4230/LIPIcs.CPM.2020.23 At
https://github.com/daikihashimoto/BWT_to_BBWT, we have some preliminary
implementations available giving empirical evidence of our conversions.

# In-Place Bijective Burrows-Wheeler Transforms

Dominik Köppl  Daiki Hashimoto  Diptarama Hendrian  Ayumi Shinohara

###### Abstract

One of the most well-known variants of the Burrows-Wheeler transform (BWT)
[Burrows and Wheeler, 1994] is the bijective BWT (BBWT) [Gil and Scott, arXiv
2012], which applies the extended BWT (EBWT) [Mantaci et al., TCS 2007] to the
multiset of Lyndon factors of a given text. Since the EBWT is invertible, the
BBWT is a bijective transform in the sense that the inverse image of the EBWT
restores this multiset of Lyndon factors such that the original text can be
obtained by sorting these factors in non-increasing order.

In this paper, we present algorithms constructing or inverting the BBWT in-
place using quadratic time. We also present conversions from the BBWT to the
BWT, or vice versa, either (a) in-place using quadratic time, or (b) in the
run-length compressed setting using
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}(n\lg r/\lg\lg r)$ time with
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}(r\lg n)$ bits of words, where $r$
is the sum of character runs in the BWT and the BBWT.

###### keywords:

In-Place Algorithms, Burrows-Wheeler transform, Lyndon words

###### category:

##  1 Introduction

The _Burrows-Wheeler transform_ (BWT) [6] is one of the most favored options
both for (a) compressing and (b) indexing data sets. On the one hand,
compression programs like bzip2 apply the BWT to achieve high compression
rates. For that, they leverage the effect that the BWT built on repetitive
data tends to have long character runs, which can be compressed by run-length
compression, i.e., representing a substring of $\ell$ a’s by the tuple
$(\texttt{a},\ell)$. On the other hand, self-indexing data structures like the
FM-index [11] enhance the BWT to a full-text self-index. A combined approach
of both compression and indexing is the run-length compressed FM-index [21],
representing a BWT with $r_{\mathsf{BWT}}$ character runs, i.e., maximal
repetitions of a character, run-length compressed in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}(r_{\mathsf{BWT}}\lg n)$ bits. This
representation can be computed directly in run-length compressed space thanks
to Policriti and Prezza [30]. The BWT and its run-length compressed
representation have been intensively studied during the past decades (e.g.,
[12, 1, 14] and the references therein). Contrary to that, a variant, called
the _bijective_ BWT (BBWT) [16], is far from being well-studied despite its
mathematically appealing characteristics111The BBWT is a bijection between
strings without the need of an artificial delimiter needed, e.g., to invert
the BWT.. As a matter of fact, we are only aware of one index data structure
based on the BBWT [3] and of two non-trivial construction algorithms [5, 2] of
the (uncompressed) BBWT, both with the need of additional data structures.

In this article, we shed more light on the connection between the BWT and the
BBWT by quadratic time in-place conversion algorithms in Sect. 5 constructing
the BWT from the BBWT, or vice versa. We can also perform these conversions in
the run-length compressed setting in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}(n\lg r/\lg\lg r)$ time with space
linear to the number of the character runs (cf. Sect. 4 and Thm. 4.1), where
$r$ is the sum of character runs in the BWT and the BBWT.

##  2 Related Work

Given a text $T$ of length $n$, the BWT of $T$ is the string obtained by
assigning $\mathsf{BWT}[i]$ to the character preceding the $i$-th
lexicographically smallest suffix of $T$ (or the last character of $T$ if this
suffix is the text itself). By this definition, we can construct the BWT with
any suffix array [22] construction algorithm. However, storing the suffix
array inherently needs $n\lg n$ bits of space. Crochemore et al. [9] tackled
this space problem with an in-place algorithm constructing the BWT in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}(n^{2})$ online on the reversed
text by simulating queries on a dynamic wavelet tree [17] that would be built
on the (growing) BWT. They also gave an algorithm for restoring the text in-
place in $\mathop{}\mathopen{}\mathcal{O}\mathopen{}(n^{2+\epsilon})$ time.

In the run-length compressed setting, Policriti and Prezza [30] can compute
the run-length compressed BWT having $r_{\mathsf{BWT}}$ character runs in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}(n\lg r_{\mathsf{BWT}})$ time while
using $\mathop{}\mathopen{}\mathcal{O}\mathopen{}(r_{\mathsf{BWT}}\lg n)$ bits
of space. They additionally presented an adaption of the wavelet tree on run-
length compressed texts, yielding a representation using
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}(r_{\mathsf{BWT}}\lg n)$ bits of
space with $\mathop{}\mathopen{}\mathcal{O}\mathopen{}(\lg r_{\mathsf{BWT}})$
query and update time. Finally, practical improvements of the run-length
compressed BWT construction were considered by Ohno et al. [29].

The BBWT is the string obtained by assigning $\mathsf{BBWT}[i]$ to the last
character of the $i$-th smallest string in the list of all conjugates of the
factors of the Lyndon factorization sorted with respect to the
$\prec_{\omega}$ order [23, Def. 4]. Bannai et al. [2] recently revealed a
connection between the bijective BWT and suffix sorting by presenting an
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}(n)$ time BBWT construction
algorithm based on SAIS [28]. With dynamic data structures like a dynamic
wavelet tree [27], Bonomo et al. [5] could devise an algorithm computing the
BBWT in $\mathop{}\mathopen{}\mathcal{O}\mathopen{}(n\lg n/\lg\lg n)$ time.
With nearly the same techniques, Mantaci et al. [24] presented an algorithm
computing the BWT (and simultaneously the suffix array if needed) from the
Lyndon factorization. All these construction algorithms need however data
structures taking $\mathop{}\mathopen{}\mathcal{O}\mathopen{}(n\lg n)$ bits of
space. However, the latter two (i.e., [5] and [24]) can work in-place by
simulating the $\mathsf{LF}$ mapping (cf. Sects. 3.4 and 3.5), which we focus
on in Sect. 5.1.

##  3 Preliminaries

Our computational model is the word RAM model with word size
$\mathop{}\mathopen{}\mathup{\Omega}\mathopen{}(\lg n)$. Accessing a word
costs $\mathop{}\mathopen{}\mathcal{O}\mathopen{}(1)$ time. An algorithm is
called _in-place_ if it uses, besides a rewriteable input, only
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}(\lg n)$ bits of working space. We
write $[{\textrm{{b}}}(I)\mathbin{{.}\,{.}}{}{\textrm{{e}}}(I)]=I$ for an
interval $I$ of natural numbers.

###  3.1 Strings

Let $\Sigma$ denote an integer alphabet of size $\sigma$ with
$\sigma=n^{\mathop{}\mathopen{}\mathcal{O}\mathopen{}(1)}$. We call an element
$T\in\Sigma^{*}$ a _string_. Its length is denoted by $|T|$. Given an integer
$j\in[1\mathbin{{.}\,{.}}{}|T|]$, we access the $j$-th character of $T$ with
$T[j]$. Concatenating a string $T\in\Sigma^{*}$ $k$ times is abbreviated by
$T^{k}$. A string $T$ is called _primitive_ if there is no string
$S\in\Sigma^{+}$ with $T=S^{k}$ for an integer $k$ with $k\geq 2$.

When $T$ is represented by the concatenation of $X,Y,Z\in\Sigma^{*}$, i.e.,
$T=\textit{XYZ}$, then $X$, $Y$ and $Z$ are called a _prefix_ , _substring_
and _suffix_ of $T$, respectively; the prefix $X$, substring $Y$, or suffix
$Z$ is called _proper_ if $X\neq T$, $Y\neq T$, or $Z\neq T$, respectively.
For two integers $i,j$ with $1\leq i\leq j\leq|T|$, let
$T[i\mathbin{{.}\,{.}}{}j]$ denote the substring of $T$ that begins at
position $i$ and ends at position $j$ in $T$. If $i>j$, then
$T[i\mathbin{{.}\,{.}}{}j]$ is the empty string. In particular, the suffix
starting at position $j$ of $T$ is called the _$j$ -th suffix_ of $T$, and
denoted with $T[j\mathbin{{.}\,{.}}{}]$. An occurrence of a substring $S$ in
$T$ is treated as a sub-interval of $[1\mathbin{{.}\,{.}}{}|T|]$ such that
$S=T[{\textrm{{b}}}(S)\mathbin{{.}\,{.}}{}{\textrm{{e}}}(S)]$. The _longest
common prefix (LCP)_ of two strings $S$ and $T$ is the longest string that is
a prefix of both $S$ and $T$.

#### Orders on Strings.

We denote the _lexicographic order_ with $\prec_{\textup{lex}}{}$. Given two
strings $S$ and $T$, $S\prec_{\textup{lex}}T$ if $S$ is a prefix of $T$ or
there exists an integer $\ell$ with $1\leq\ell\leq\min(|S|,|T|)$ such that
$S[1\mathbin{{.}\,{.}}{}\ell-1]=T[1\mathbin{{.}\,{.}}{}\ell-1]$ and
$S[\ell]<T[\ell]$. Next we define the _$\prec_{\omega}{}$ order_ of strings,
which is based on the lexicographic order of infinite strings: We write
$S\prec_{\omega}{}T$ if the infinite concatenation $S^{\omega}:={SSS}\cdots$
is lexicographically smaller than $T^{\omega}:={TTT}\cdots$. For instance,
$\texttt{ab}\prec_{\textup{lex}}\texttt{aba}$ but
$\texttt{aba}\prec_{\omega}\texttt{ab}$.

#### Rank and Select Queries.

Given a string $T\in\Sigma^{*}$, a character $\texttt{c}\in\Sigma$, and an
integer $j$, the _rank_ query $T.{\textrm{{rank}}}_{\texttt{c}}(j)$ counts the
occurrences of c in $T[1\mathbin{{.}\,{.}}{}j]$, and the _select_ query
$T.{\textrm{{select}}}_{\texttt{c}}(j)$ gives the position of the $j$-th c in
$T$. We stipulate that
${\textrm{{rank}}}_{\texttt{c}}(0)={\textrm{{select}}}_{\texttt{c}}(0)=0$. A
_wavelet tree_ is a data structure supporting rank and select queries.

###  3.2 Lyndon Words

Given a string $T=T[1\mathbin{{.}\,{.}}{}n]$, its $i$-th _conjugate_
${\textrm{{conj}}}_{i}(T)$ is defined as
$T[i+1\mathbin{{.}\,{.}}{}n]T[1\mathbin{{.}\,{.}}{}i]$ for an integer
$i\in[0\mathbin{{.}\,{.}}{}n-1]$. We say that $T$ and all of its conjugates
belong to the _conjugate class_
${\textrm{{conj}}}(T):=\\{{\textrm{{conj}}}_{0}(T),\ldots,{\textrm{{conj}}}_{n-1}(T)\\}$.
If a conjugate class contains _exactly_ one conjugate that is
lexicographically smaller than all other conjugates, then this conjugate is
called a _Lyndon word_ [20]. Equivalently, a string $T$ is said to be a Lyndon
word if and only if $T\prec_{\textup{lex}}S$ for every proper suffix $S$ of
$T$ [10, Prop. 1.2].

The _Lyndon factorization_ [8] of $T\in\Sigma^{+}$ is the factorization of $T$
into a sequence of lexicographically non-increasing Lyndon words $T_{1}\cdots
T_{t}$, where (a) each $T_{x}\in\Sigma^{+}$ is a Lyndon word for
$x\in[1\mathbin{{.}\,{.}}{}t]$, and (b) $T_{x}\succeq_{\textup{lex}}T_{x+1}$
for each $x\in[1\mathbin{{.}\,{.}}{}t)$. Each Lyndon word $T_{x}$ is called a
_Lyndon factor_.

######  Lemma 3.1 ([10, Algo. 2.1]).

Given a string $T$ of length $n$, there is an algorithm that outputs the
Lyndon factors $T_{1},\ldots,T_{t}$ one by one in increasing order in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}(n)$ total time while keeping only
a constant number of pointers to positions in $T$ that (a) can move one
position forward at one time or (b) can be set to the position of another
pointer.

######  Proof 3.2.

The algorithm of Duval uses three variables $i$, $j$, and $k$ (cf. Algorithm 1
in the appendix) pointing to text positions. $k$ is the ending position of the
previously computed Lyndon factor (or zero at the beginning). On each step,
$j\in[k+2\mathbin{{.}\,{.}}{}n]$ is incremented by one, while $i$ is either
incremented by one or reset to $k+1$, as long as
$T[k+1\mathbin{{.}\,{.}}{}i-1]=T[j-(i-k)\mathbin{{.}\,{.}}{}j-1]$ is a prefix
of a Lyndon word starting at $T[k+1\mathbin{{.}\,{.}}{}]$. If
$T[k+1\mathbin{{.}\,{.}}{}i]$ is no longer such a prefix, then
$T[k+1\mathbin{{.}\,{.}}{}i-1]$ is either a Lyndon factor or a repetition of
Lyndon factors, each of length $j-i$. In total, we visit at most $2n$
characters by incrementing the text positions $i$, $j$, and $k$.

For what follows, we fix a string $T[1\mathbin{{.}\,{.}}{}n]$ over an alphabet
$\Sigma$ with size $\sigma$. We use the string $T:=\texttt{bacabbabb}$ as our
running example. Its Lyndon factors are $T_{1}=\texttt{b}$,
$T_{2}=\texttt{ac}$, $T_{3}=\texttt{abb}$, and $T_{4}=\texttt{abb}$.

Figure 1: All three BWT variants studied in this paper applied on our running
example $T=\texttt{bacabbabb}$. _Left_ : $\mathsf{BBWT}$ built on the last
characters of the conjugates of all Lyndon words sorted in the
$\prec_{\omega}$ order. _Middle_ and _Right_ : $\mathsf{BWT}^{\circ}$ and
$\mathsf{BWT}$ built on the lexicographically sorted conjugates of $T$ and of
$T\texttt{\$}$, respectively. To ease understanding, each character is marked
with its position in $T$ in subscript. Reading these positions in $\mathsf{F}$
of $\mathsf{BBWT}$ and in $\mathsf{F}$ of $\mathsf{BWT}$ gives a circular
suffix array (there are multiple possibilities with
$T_{3}=T_{4}=\texttt{abb}$) and the suffix array (the position of $ is
uniquely defined as $|T\texttt{\$}|=10$).

###  3.3 Burrows-Wheeler Transforms

We denote the bijective BWT of $T$ by $\mathsf{BBWT}$, where
$\mathsf{BBWT}[i]$ is the last character of the $i$-th string in the list
storing the conjugates of all Lyndon factors $T_{1},\ldots,T_{t}$ of $T$
sorted with respect to the $\prec_{\omega}$ order. A property of
$\mathsf{BBWT}$ used in this paper as a starting point for an inversion
algorithm is the following:

######  Lemma 3.3 ([5, Lemma 15]).

$\mathsf{BBWT}[1]=T[n]$.

######  Proof 3.4.

There is no conjugate of a Lyndon factor that is smaller than the smallest
Lyndon factor $T_{t}$ since
$T_{t}\preceq_{\textup{lex}}T_{x}\prec_{\textup{lex}}T_{x}[j\mathbin{{.}\,{.}}{}]$
for every $j\in[2\mathbin{{.}\,{.}}{}|T_{x}|]$ and every
$x\in[1\mathbin{{.}\,{.}}{}t]$. Therefore, $T_{t}$ is the smallest string
among all conjugates of all Lyndon factors. Hence, $\mathsf{BBWT}[1]$ is the
last character of $T_{t}$, which is $T[n]$.

The BWT of $T$, called in the following $\mathsf{BWT}$, is the BBWT of
$\texttt{\$}T$ for a delimiter $\texttt{\$}\not\in\Sigma$ smaller than all
other characters in $T$ (cf. [15, Lemma 12] since $\texttt{\$}T$ is a Lyndon
word). Originally, the BWT is defined by reading the last characters of all
cyclic rotations of $T$ (without $) sorted lexicographically [6]. Here, we
call the resulting string $\mathsf{BWT}^{\circ}$. $\mathsf{BWT}^{\circ}$ is
equivalent to $\mathsf{BWT}$ if $T$ contains the aforementioned unique
delimiter $. We further write $\mathsf{BWT}_{P}$ (and analogously
$\mathsf{BBWT}_{P}$ or $\mathsf{BWT}^{\circ}_{P}$) to denote the BWT of $P$
for a string $P$.

Since $\mathsf{BWT}$ (and analogously $\mathsf{BBWT}$ or
$\mathsf{BWT}^{\circ}$) is a permutation of $T$, it is natural to identify
each entry of $\mathsf{BWT}$ with a text position: By construction
$\mathsf{BWT}[i]=T[j]$, where $T[j+1\mathbin{{.}\,{.}}{}]$ is the $i$-th
lexicographically smallest suffix, i.e., $\mathsf{SA}[i]=j+1$, where
$\mathsf{SA}$ is the suffix array of $T$. A similar relation is given between
$\mathsf{BBWT}$ and the circular suffix array [19, 2], which is uniquely
defined up to positions of equal Lyndon factors. Figure 1 gives an example for
all three variants. In what follows, we review means to simulate a linear
traversal of the text in forward or backward manner by $\mathsf{BWT}$, and
then translate this result to $\mathsf{BBWT}$.

###  3.4 Backward and Forward Steps

Having the location of $T[i]$ in $\mathsf{BWT}$, we can compute $T[i+1]$
(i.e., $T[1]$ for $i=1$) and $T[i-1]$ (i.e., $T[n]$ for $i=0$) by rank and
select queries. To move from $T[i]$ to $T[i+1]$, which we call a _forward
step_ , we can use the $\mathsf{FL}$ mapping:

$\mathsf{FL}[i]:=\mathsf{BWT}.{\textrm{{select}}}_{\mathsf{F}[i]}(\mathsf{F}.{\textrm{{rank}}}_{\mathsf{F}[i]}(i)),$
(1)

where $\mathsf{F}[i]$ is the $i$-th lexicographically smallest character in
$\mathsf{BWT}$. To move from $T[i]$ to $T[i-1]$, we can use the _backward
step_ of the FM-index [11], which is also called $\mathsf{LF}$ mapping, and is
defined as follows:

$\mathsf{LF}[i]:=\mathsf{F}.{\textrm{{select}}}_{\mathsf{BWT}[i]}(\mathsf{BWT}.{\textrm{{rank}}}_{\mathsf{BWT}[i]}(i))=C[\mathsf{BWT}[i]]+\mathsf{BWT}.{\textrm{{rank}}}_{\mathsf{BWT}[i]}(i),$
(2)

where $C[c]$ is the number of occurrences of those characters in
$\mathsf{BWT}$ that are smaller than $c$ (for each character
$c\in[1\mathbin{{.}\,{.}}{}\sigma]$). We observe from the second equation of
(2) that there is no need for $\mathsf{F}$ when having $C$. This is important,
as we can compute $C[i]$ in $\mathop{}\mathopen{}\mathcal{O}\mathopen{}(n)$
time only having $\mathsf{BWT}$ available. Hence, we can compute
$\mathsf{LF}[i]$ in $\mathop{}\mathopen{}\mathcal{O}\mathopen{}(n)$ time in-
place. However, the same trick does not work with
$\mathsf{FL}[i]=\mathsf{BWT}.{\textrm{{select}}}_{\mathsf{F}[i]}(i-C[\mathsf{F}[i]])$.
To lookup $\mathsf{F}[i]$, we can use the selection algorithm of Chan et al.
[7] using $\mathsf{BWT}$ and $\mathop{}\mathopen{}\mathcal{O}\mathopen{}(\lg
n)$ bits as working space (the algorithm restores $\mathsf{BWT}$ after
execution) to compute an entry of $\mathsf{F}$ in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}(n)$ time.

In summary, we can compute both $\mathsf{FL}[i]$ and $\mathsf{LF}[i]$ in-place
in $\mathop{}\mathopen{}\mathcal{O}\mathopen{}(n)$ time. The algorithm of
Crochemore et al. [9, Thm. 2] inverting $\mathsf{BWT}$ in-place in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}(n^{2+\epsilon})$ time uses the
result of Munro and Raman [26] computing $\mathsf{F}[i]$ in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}(n^{1+\epsilon})$ time for a
constant $\epsilon>0$ in the comparison model. As noted by Chan et al. [7,
Sect. 1], the time bound for the inversion can be improved to
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}(n^{2})$ time in the RAM model
under the assumption that $\mathsf{BWT}$ is rewritable.

If we allow more space, it is still advantageous to favor storing $C$ instead
of $\mathsf{F}$ if $\sigma=\mathop{}\mathopen{}o\mathopen{}(n)$ because
storing $\mathsf{F}$ and $C$ in their plain forms take $n\lg\sigma$ bits and
$\sigma\lg n$ bits, respectively. To compute $\mathsf{FL}[i]$, we can also
compute $\mathsf{FL}$ without $\mathsf{F}$ by endowing $C$ with a predecessor
data structure (which we do in Sect. 4.3).

Finally, we also need $\mathsf{LF}$ and $\mathsf{FL}$ on $\mathsf{BBWT}$ for
our conversion algorithms. We can define $\mathsf{LF}$ and $\mathsf{FL}$
similarly for $\mathsf{BBWT}$ with the following peculiarity:

###  3.5 Steps in the Bijective BWT

The major difference to the BWT is that the LF mapping of the BBWT can contain
multiple cycles, meaning that $\mathsf{LF}$ (or $\mathsf{FL}$) recursively
applied to a $\mathsf{BBWT}$ position would result in searching circular (more
precisely, the search stays within the same Lyndon factor). This is because
$\mathsf{BBWT}$ is the extended BWT [23, Thm. 20 and Remark 12] applied to the
multiset of Lyndon factors $\\{T_{1},\ldots,T_{t}\\}$. This fact was exploited
for circular pattern matching [19], but is not of interest here.

Instead, we follow the analysis of the so-called _rewindings_ [3, Sect. 3]:
Remembering that we store the last character of all conjugates of all Lyndon
factors in $\mathsf{BBWT}$, we observe that the entries in $\mathsf{BBWT}$
representing the Lyndon factors (i.e., the last characters of the Lyndon
factors) are in sorted order (starting with $T_{t}[|T_{t}|]$ and ending with
$T_{1}[|T_{1}|]$). That is because the lexicographic order and the
$\prec_{\omega}$ order are the same for Lyndon words [5, Thm. 8]. Applying the
backward step at such an entry results in a rewinding, i.e., we can move from
the beginning of a Lyndon factor $T_{x}$ (represented by $T_{x}[|T_{x}|]$ in
$\mathsf{BBWT}$) to the end of $T_{x}$ (represented by $T_{x}[1]$ in
$\mathsf{BBWT}$) with one backward step. We use this property with Lemma 3.3
in the following sections to read the Lyndon factors from $T$ individually in
the order $T_{t},\ldots,T_{1}$.

##  4 Run-Length Compressed Conversions

We now consider $\mathsf{BWT}$ and $\mathsf{BBWT}$ represented as run-length
compressed strings taking
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}(r_{\mathsf{BWT}}\lg n)$ and
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}(r_{\mathsf{BBWT}}\lg n)$ bits of
space, where $r_{\mathsf{BWT}}$ and $r_{\mathsf{BBWT}}$ are the number of
character runs in $\mathsf{BWT}$ and $\mathsf{BBWT}$, respectively. For
$r:=\max(r_{\mathsf{BWT}},r_{\mathsf{BBWT}})$, the goal of this section is the
following:

######  Theorem 4.1.

We can convert $\mathsf{RLBBWT}$ to $\mathsf{RLBWT}$ in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}(n\lg r/\lg\lg r)$ time using
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}(r\lg n)$ bits as working space, or
vice versa.

To prove this theorem, we need a data structure that works in the run-length
compressed space while supporting rank and select queries as well as updates
more efficiently than the $\mathop{}\mathopen{}\mathcal{O}\mathopen{}(n)$ time
in-place approach described in Sects. 3.4 and 3.5:

###  4.1 Run-length Compressed Wavelet Trees

Given a run-length compressed string $S$ of uncompressed length $n$ with $r$
character runs, there is an $\mathop{}\mathopen{}\mathcal{O}\mathopen{}(r\lg
n)$ bits representation of $S$ that supports access, rank, select, insertions,
and deletions in $\mathop{}\mathopen{}\mathcal{O}\mathopen{}(\lg r)$ time [30,
Lemma 1]. It consists of (1) a dynamic wavelet tree maintaining the starting
characters of each character run and (2) a dynamic Fenwick tree maintaining
the lengths of the runs. It can be accelerated to
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}(\lg r/\lg\lg r)$ time by using the
following representations:

  1. 1.

The dynamic wavelet tree of Navarro and Nekrich [27] on a text of length $r$
uses $\mathop{}\mathopen{}\mathcal{O}\mathopen{}(r\lg r)$ bits, and supports
both updates and queries in $\mathop{}\mathopen{}\mathcal{O}\mathopen{}(\lg
r/\lg\lg r)$ time.

  2. 2.

The dynamic Fenwick tree of Bille et al [4, Thm. 2] on $r$ $(\lg n)$-bit
numbers uses $\mathop{}\mathopen{}\mathcal{O}\mathopen{}(r\lg n)$ bits, and
supports both updates and queries in constant time if updates are restricted
to be in-/decremental.

The obtained time complexity of this data structure directly improves the
construction of $\mathsf{RLBWT}$:

######  Corollary 4.2 ([30, Thm. 2]).

We can construct the $\mathsf{RLBWT}$ in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}(r_{\mathsf{BWT}}\lg n)$ bits of
space online on the reversed text in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}(n\lg r_{\mathsf{BWT}}/\lg\lg
r_{\mathsf{BWT}})$ time.

In the run-length compressed wavelet tree representation, $\mathsf{RLBWT}$ and
$\mathsf{RLBBWT}$ support an update operation and a backward step in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}(\lg r/\lg\lg r)$ time with
$r:=\max(r_{\mathsf{BWT}},r_{\mathsf{BBWT}})$. This helps us to devise the
following two conversions:

###  4.2 From $\mathsf{RLBBWT}$ to $\mathsf{RLBWT}$

We aim for directly outputting the characters of $T$ in reversed order since
we can then use the algorithm of Cor. 4.2 building $\mathsf{RLBWT}$ online on
the reversed text. We start with the first entry of $\mathsf{BBWT}$
(corresponding to the last Lyndon factor $T_{t}$, i.e., storing
$T_{t}[|T_{t}|]=T[n]$ according to Lemma 3.3) and do a backward step until we
come back at this first entry (i.e., we have visited all characters of
$T_{t}$). During that search, we copy the read characters to $\mathsf{RLBWT}$
and mark in an array $R$ of length $r_{\mathsf{BBWT}}$ at entry $i$ how often
we visited the $i$-th character run of $\mathsf{RLBBWT}$. Finally, we remove
the read cycle of $\mathsf{RLBBWT}$ by decreasing the run lengths of
$\mathsf{RLBBWT}$ by the numbers stored in $R$. By doing so, we remove the
last Lyndon factor $T_{t}$ from $\mathsf{RLBBWT}$ and consequently know that
the currently first entry of $\mathsf{BBWT}$ must correspond to $T_{t-1}$.
This means that we can apply the algorithm recursively on the remaining
$\mathsf{RLBBWT}$ to extract and delete the Lyndon factors in reversed order
while building $\mathsf{RLBWT}$ in the meantime. By removing $T_{t}$,
$\mathsf{BBWT}$ is still a valid BBWT since $\mathsf{BBWT}$ becomes the BBWT
of $T^{\prime}:=T_{1}\cdots T_{t-1}$ whose Lyndon factors are the same as of
$T$ (but without $T_{t}$). Note that it is also possible to build
$\mathsf{RLBWT}$ in forward order, i.e., computing
$\mathsf{RLBWT}_{T_{1}\cdots T_{x}}$ for increasing $x$ by applying the
algorithm of Mantaci et al. [24, Fig. 1] while omitting the suffix array
construction.

###  4.3 From $\mathsf{RLBWT}$ to $\mathsf{RLBBWT}$

To build $\mathsf{BBWT}$, we need to be aware of the Lyndon factors of $T$,
which we compute with Lemma 3.1 by simulating a forward scan on $T$ with
$\mathsf{FL}$ on $\mathsf{BWT}$. To this end, we store the entries of the $C$
array in a Fusion tree [13] using
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}(\sigma\lg n)$ bits and supporting
predecessor search in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}(\lg\sigma/\lg\lg\sigma)=\mathop{}\mathopen{}\mathcal{O}\mathopen{}(\lg
r/\lg\lg r)$ time.222We assume that the alphabet $\Sigma$ is _effective_ ,
i.e., that each character of $\Sigma$ appears at least once in $T$. Otherwise,
assume that $T$ uses $\sigma^{\prime}$ characters. Then we build the static
dictionary of Hagerup [18] in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}(\sigma^{\prime}\lg\sigma^{\prime})$
time, supporting access to a character in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}(\lg\lg\sigma^{\prime})=\mathop{}\mathopen{}\mathcal{O}\mathopen{}(\lg\lg
r)$ time, assigning each of the $\sigma^{\prime}$ characters an integer from
$[1\mathbin{{.}\,{.}}{}\sigma^{\prime}]$. We further map $\mathsf{RLBWT}$ to
the alphabet $[1\mathbin{{.}\,{.}}{}\sigma^{\prime}]$, which can be done in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}(r)$ time by using
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}(r\lg n)$ space for a linear-time
integer sorting algorithm.  This time complexity also covers a forward step in
$\mathsf{RLBWT}$ by simulating $\mathsf{F}$ with the Fusion tree on $C$.
Hence, this fusion tree allows us to apply Lemma 3.1 computing the Lyndon
factorization of $T$ with a multiplicative
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}(\lg r/\lg\lg r)$ time penalty
since this algorithm only needs to perform forward traversals. The starting
point of such a traversal is the position $i$ with
$\mathsf{BWT}[i]=\texttt{\$}$ because $\mathsf{FL}[i]$ returns the first
character of $T$. Whenever we detect a Lyndon factor $T_{x}$ (starting with
$x=1$), we copy this factor to our dynamic $\mathsf{RLBBWT}$. For that, we
always maintain the first and the last position of $T_{x}$ in memory. Having
the last position of $T_{x}$, we perform backward steps on $\mathsf{RLBWT}$
until returning at the first position of $T_{x}$ to read the characters of
$T_{x}$ in reversed order. Then we continue with the algorithm of Lemma 3.1 at
the position after $T_{x}$ (for recursing on $T_{x+1}$). Inserting a Lyndon
factor into $\mathsf{RLBBWT}$ works exactly as sketched by Bonomo et al. [5,
Thm. 17] or in Algorithm 2 in the appendix (we review this algorithm in detail
in Sect. 5.1).

##  5 In-Place Conversions

We finally present our in-place conversions that work in quadratic time by
computing $\mathsf{LF}$ or $\mathsf{FL}$ in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}(n)$ time having only stored either
$\mathsf{BWT}$, $\mathsf{BBWT}$, or $\mathsf{BWT}^{\circ}$. We note that the
constructions from the text also work in the comparison model, while inverting
a transform or converting two different transforms have a multiplicative
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}(n^{\epsilon})$ time penalty as the
fastest option to access $\mathsf{F}$ in the comparison model uses
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}(n^{1+\epsilon})$ time for a
constant $\epsilon>0$ [26]. We start with the construction and inversion of
$\mathsf{BWT}^{\circ}$ (Sects. 5.1 and 5.2), where we show (a) that we can
construct $\mathsf{BWT}^{\circ}$ from the text in the same manner as Bonomo et
al. [5] construct $\mathsf{BBWT}$, and (b) that the latter construction works
also in-place. Next, we show in Sect. 5.3 how to invert $\mathsf{BBWT}$ with
the BWT inversion algorithm of Crochemore et al. [9, Fig. 3], which allows us
to also convert $\mathsf{BBWT}$ to $\mathsf{BWT}$ with the BWT construction
algorithm of the same paper [9, Fig. 2]. Finally, we show a conversion from
$\mathsf{BWT}$ to $\mathsf{BBWT}$ in Sect. 5.4. An overview is given in Table
1.

To From $T$ $\mathsf{BWT}$ $\mathsf{BBWT}$ $\mathsf{BWT}^{\circ}$ $T$ \ [9,
Fig. 3] Sect. 5.3 Sect. 5.2 $\mathsf{BWT}$ [9, Fig. 2] \ Sect. 5.3
$\mathsf{BBWT}$ Sect. 5.1 Sect. 5.4 \ $\mathsf{BWT}^{\circ}$ Sect. 5.1 \

Table 1: Overview of in-place conversions in focus of Sect. 5 working in
quadratic time.

###  5.1 Constructing $\mathsf{BWT}^{\circ}$ and $\mathsf{BBWT}$

We can compute $\mathsf{BWT}^{\circ}$ and $\mathsf{BBWT}$ from $T$ with the
algorithm of Bonomo et al. [5] computing the extended BWT [23]. The extended
BWT is the BWT defined on a set of primitive strings. As stated in Sect. 3.5,
the extended BWT coincides with $\mathsf{BBWT}$ if this set of primitive
strings is the set of Lyndon factors of $T$ [5, Thm. 14]. We briefly describe
the algorithm of Bonomo et al. [5] for computing the BBWT (cf. Fig. 2 and
Algorithm 2 in the appendix): For each Lyndon factor $T_{x}$ (starting with
$x=1$), prepend $T_{x}[|T_{x}|]$ to $\mathsf{BBWT}$. To insert the remaining
characters of the factor $T_{x}$, let $p\leftarrow 1$ be the position of the
currently inserted character. Then perform, for each $j=|T_{x}|-1$ down to
$1$, a backward step $p\leftarrow\mathsf{LF}[p]+1$, and insert $T_{x}[j]$ at
$\mathsf{BBWT}[p]$ (cf. Algorithm 2 in the appendix). To understand why this
computes $\mathsf{BBWT}$, we observe that the last character of the most
recently inserted Lyndon factor $T_{x}$ is always the first character in
$\mathsf{BBWT}_{T_{1}\cdots T_{x}}$ according to Lemma 3.3. By recursively
inserting the preceding character at the place returned by a backward step, we
precisely insert this character at the position where we would expect it
(another backward step from the same position $p$ would then return the
inserted character). Using only $n$ backward steps and $n$ insertions, this
algorithm works in-place in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}(n^{2})$ time by simulating
$\mathsf{LF}$ as described in Sect. 3.4.

Consequently, we can build $\mathsf{BWT}^{\circ}$ if $T$ is a Lyndon word
since in this case $\mathsf{BWT}^{\circ}$ and $\mathsf{BBWT}$ coincide [15,
Lemma 12]. That is because sorting the suffixes of $T$ is equivalent to
sorting the conjugates of $T$ (if $T$ is a Lyndon word, then its Lyndon
factorization consists only of $T$ itself).

It is easy to generalize this to work for a general string $T$. First, if $T$
is primitive, then we compute its so-called _Lyndon conjugate_ , i.e., a
conjugate of $T$ that is a Lyndon word. (The Lyndon conjugate of $T$ is
uniquely defined if $T$ is primitive.) We can find the Lyndon conjugate of $T$
in $\mathop{}\mathopen{}\mathcal{O}\mathopen{}(n)$ time with the following two
lemmata:

######  Lemma 5.1 ( [10, Prop. 1.3] ).

Given two Lyndon words $S$ and $T$, $ST$ is a Lyndon word if
$S\prec_{\textup{lex}}T$.

######  Lemma 5.2.

Given a primitive string $T$, we can find its Lyndon conjugate in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}(n)$ time with
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}(\lg n)$ bits of space.

######  Proof 5.3.

We use Lemma 3.1 to detect the last Lyndon factor $T_{t}$ of the Lyndon
factorization $T_{1}\cdots T_{t}$ of $T$ with
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}(\lg n)$ bits of working space.
According to Lemma 5.1, $T_{t}T_{1}$ is a Lyndon word since
$T_{t}\prec_{\textup{lex}}T_{1}$, and so is $T_{t}T_{1}\cdots T_{t-1}$ a
Lyndon word by a recursive argument. Hence, we have found $T$’s Lyndon
conjugate.

Let be the Lyndon conjugate of $T$ for $j\in[0\mathbin{{.}\,{.}}{}n-1]$. Since
$\mathsf{BWT}^{\circ}$ is identical to $\mathsf{BBWT}$, we are done by running
the algorithm of Bonomo et al. [5] on . Finally, if $T$ is not primitive, then
there is a primitive string $P$ such that $T=P^{k}$ for an integer $k\geq 2$.
We can compute $\mathsf{BWT}^{\circ}_{P}$ with the above considerations. For
obtaining $\mathsf{BWT}^{\circ}$, according to [25, Prop. 2], we only need to
make each character in $\mathsf{BWT}^{\circ}_{P}$ to a character run of length
$k$, i.e., if $\mathsf{BWT}^{\circ}_{P}[i]=\texttt{c}$, we append
$\texttt{c}^{k}$ to $\mathsf{BWT}^{\circ}$ for increasing
$i\in[1\mathbin{{.}\,{.}}{}|P|]$ (cf. [15, Thm. 13]). Checking whether $T$ is
primitive can be done in $\mathop{}\mathopen{}\mathcal{O}\mathopen{}(n^{2})$
time by checking for each pair of positions their longest common prefix. We
summarized these steps in the pseudo code of Algorithm 4 in the appendix.

Figure 2: Computing $\mathsf{BBWT}$ from our running example
$T=\texttt{bacabbabb}$ in four steps (visualized by four columns separated by
three arrows  ), cf. Sect. 5.1. In each column, the characters from the top to
the solid horizontal line (  ) form the currently built BBWT. The characters
below that up to the dashed horizontal line (  ) are under consideration of
being merged into BBWT. This dashed line is always before the beginning of the
next yet unread Lyndon factor. _First column_ : We have already computed the
BBWT of $T_{1}T_{2}=\texttt{bac}$, which is cba. In the following we want to
add the next Lyndon factor $T_{3}=\texttt{abb}$ to it. For that, we prepend
its last character to the currently constructed BBWT. _Second column_ : We
move the last character above the dashed line to the position
${\color[rgb]{0.796875,0.29296875,0.0859375}\definecolor[named]{pgfstrokecolor}{rgb}{0.796875,0.29296875,0.0859375}\mathsf{LF}}[{\color[rgb]{0.5234375,0.6015625,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5234375,0.6015625,0}p}]+1$
with
${\color[rgb]{0.5234375,0.6015625,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5234375,0.6015625,0}p}=1$,
and update
${\color[rgb]{0.5234375,0.6015625,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5234375,0.6015625,0}p}\leftarrow{\color[rgb]{0.796875,0.29296875,0.0859375}\definecolor[named]{pgfstrokecolor}{rgb}{0.796875,0.29296875,0.0859375}\mathsf{LF}}[{\color[rgb]{0.5234375,0.6015625,0}\definecolor[named]{pgfstrokecolor}{rgb}{0.5234375,0.6015625,0}p}]+1$.
We recurse in the _third column_ , and have produced the BBWT of
$T_{1}T_{2}T_{3}=\texttt{bacabb}$ in the _forth column_.

###  5.2 Inverting $\mathsf{BWT}^{\circ}$

To invert $\mathsf{BWT}^{\circ}$, we use the techniques of Crochemore et al.
[9, Fig. 3] inverting $\mathsf{BWT}$ in-place in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}(n^{2})$ time. An invariant is that
the BWT entry, whose $\mathsf{FL}$ mapping corresponds to the next character
to output, is marked with a unique delimiter $. Given that
$\mathsf{BWT}[i]=\texttt{\$}$, the algorithm outputs
$\mathsf{BWT}[\mathsf{FL}[i]]$, sets
$\mathsf{BWT}[\mathsf{FL}[i]]\leftarrow\texttt{\$}$, removes
$\mathsf{BWT}[i]$, and recurses until $ is the last character remaining in
$\mathsf{BWT}$. By doing so, it restores the text in text order.

To adapt this algorithm for inverting $\mathsf{BWT}^{\circ}$, we additionally
need a pointer $p$ storing the first symbol of the text (since there is no
unique delimiter such as $ in general). Given that $p$ points to
$\mathsf{BWT}^{\circ}[i]$, we set $i\leftarrow\mathsf{FL}[i]$ and subsequently
output $\mathsf{BWT}^{\circ}[i]$. From now on, the algorithm works exactly as
[9, Fig. 3] if we set $\mathsf{BWT}^{\circ}[i]\leftarrow\texttt{\$}$ after
outputting $\mathsf{BWT}^{\circ}[i]$ (cf. Algorithm 5 in the appendix). More
involving is inverting $\mathsf{BBWT}$ or converting $\mathsf{BBWT}$ to
$\mathsf{BWT}$, which we tackle next.

Figure 3: Inverting $\mathsf{BBWT}$ of our running example
$T=\texttt{bacabbabb}$ (cf. Sect. 5.3). _First Column_ : We prepend the $
delimiter to the last Lyndon factor $T_{t}$ by inserting $ at
$\mathsf{BBWT}[2]$. A forward step symbolized by the dashed arrow (  ) leads
us from $ to the first character of $T_{t}$. _Second Column_ : We output
$\mathsf{BBWT}[6]=T_{t}[1]=T[7]$, remove $ and update
$\mathsf{BBWT}[6]\leftarrow\texttt{\$}$. The output is appended to the string
shown below the dashed horizontal line (  ). We continue with a forward step
to access $\mathsf{BBWT}[4]=T_{t}[2]=T[8]$, and recurse in the _third column_.
_Forth Column_ : Since a forward step returns $, we know that we have
successfully extracted $T_{t}=\texttt{abb}$.

###  5.3 Inverting $\mathsf{BBWT}$

Similarly to Sect. 4.2, we read the Lyndon factors from $\mathsf{BBWT}$ in the
order $T_{t},\ldots,T_{1}$, and move each read Lyndon factor directly to a
text buffer such that while reading the last Lyndon factor $T_{x}$ for an
$x\in[1\mathbin{{.}\,{.}}{}t]$ from $\mathsf{BBWT}_{T_{1}\cdots T_{x}}$, we
move the characters of $T_{x}$ to $T_{x+1}\cdots T_{t}$, producing
$\mathsf{BBWT}_{T_{1}\cdots T_{x-1}}$ and $T_{x}\cdots T_{t}$. This allows us
to recurse by reading always the last Lyndon factor $T_{x}$ stored in
$\mathsf{BBWT}_{T_{1}\cdots T_{x}}$.

Here, we want to apply the inversion algorithm for $\mathsf{BWT}^{\circ}$
described in Sect. 5.3. For adapting this algorithm to work with
$\mathsf{BBWT}$, it suffices to insert $ at $\mathsf{BBWT}[2]$ (cf. Fig. 3).
By doing so, we add $ to the cycle of the currently last Lyndon factor $T_{x}$
stored in $\mathsf{BBWT}$, i.e., we enlarge the Lyndon factor $T_{x}$ to
$\texttt{\$}T_{x}$. That is because (a) $\mathsf{BBWT}[1]$ corresponds to the
last character $T_{x}[|T_{x}|]$ of $T_{x}$ (cf. Lemma 3.3), and after
inserting $, $\mathsf{F}[1]=\texttt{\$},\mathsf{F}[2]=T_{x}[1]$, hence
$\mathsf{FL}[1]=2$ (a forward step on the last character of $T_{x}$ gives $)
and $\mathsf{FL}[2]$ gives the position in $\mathsf{BBWT}$ corresponding to
$T_{x}[1]$. Moreover, inserting $ makes $\mathsf{BBWT}$ the BBWT of
$T^{\prime}:=T_{1}\cdots T_{x_{1}}\texttt{\$}T_{x}$, where $\texttt{\$}T_{x}$
is the last Lyndon factor of $T^{\prime}$. We now use the property that
$\texttt{\$}T_{x}[i\mathbin{{.}\,{.}}{}|T_{x}|]$ is a Lyndon word for each
$i\in[1\mathbin{{.}\,{.}}{}|T_{x}|]$, allowing us to perform the inversion
steps of Crochemore et al. [9, Fig. 3] on $\mathsf{BBWT}{}$. By doing so, we
can remove the entry of $\mathsf{BBWT}$ corresponding to

######  Conjecture 4 (j).

T_x for increasing $j\in[0\mathbin{{.}\,{.}}{}|T_{x}|-1]$ and prepend the
extracted characters to the text buffer storing $T_{x+1}\cdots T_{t}$ within
our working space while keeping $\mathsf{BBWT}$ a valid BBWT.

Instead of inverting $\mathsf{BBWT}$, we can convert $\mathsf{BBWT}$ to
$\mathsf{BWT}$ in-place by running the in-place BWT construction algorithm of
Crochemore et al. [9, Fig. 2] on the text buffer after the extraction of each
Lyndon factor. Unfortunately, this works not character-wise, but needs a
Lyndon factor to be fully extracted before inserting its characters into
$\mathsf{BWT}$. Interestingly, for the other direction (from $\mathsf{BWT}$ to
$\mathsf{BBWT}$), we can propose a different kind of conversion that works
directly on $\mathsf{BWT}$ without decoding it.

###  5.4 From $\mathsf{BWT}$ to $\mathsf{BBWT}$ on the Fly

Like in Sect. 4.3, we process the Lyndon factors of $T$ individually to
compute $\mathsf{BBWT}$ by scanning $\mathsf{BWT}$ in text order to simulate
Lemma 3.1. Suppose that we have built $\mathsf{BWT}$ on
$T\texttt{\$}\not=\texttt{\$}$ with $ being the $(t+1)$-th Lyndon factor of
$T\texttt{\$}$, and suppose that we have detected the first Lyndon factor
$T_{1}$. Let f denote the last character of $T_{1}$.333f stands for final
character. Further let $i_{\texttt{f}}$ and $i_{\texttt{\$}}$ be the position
of the last character of $T_{1}$ and the last character of $T$, respectively,
such that $\mathsf{BWT}[i_{\texttt{f}}]=\texttt{f}$ and
$\mathsf{BWT}[i_{\texttt{\$}}]=\texttt{\$}$. Let
$p:=\mathsf{LF}[i_{\texttt{f}}]$ such that $\mathsf{F}[p]=\texttt{f}$ and
$\mathsf{BWT}[p]=T_{1}[|T_{1}|-1]$ if $|T_{1}|>1$ or
$\mathsf{BWT}[p]=\texttt{\$}$ otherwise. Since $T_{1}$ and $T_{2}$ are Lyndon
factors, $T_{1}\succeq_{\textup{lex}}T_{2}$. Consequently, the suffix
$T[{\textrm{{b}}}(T_{2})\mathbin{{.}\,{.}}{}]$ (the context of
$\mathsf{BWT}[i_{\texttt{f}}]$) is lexicographically smaller than the suffix
$T[{\textrm{{b}}}(T_{1})\mathbin{{.}\,{.}}{}]$ (the context of
$\mathsf{BWT}[i_{\texttt{\$}}]$), i.e., $i_{\texttt{f}}<i_{\texttt{\$}}$.
Figure 4 gives an overview of the introduced setting.

Figure 4: Setting of Sect. 5.4 with focus on forming a cycle for a Lyndon
factor ending with f in $\mathsf{BWT}$. _Left_ : We exchange
$\mathsf{BWT}[i_{\texttt{f}}]$ with $\mathsf{BWT}[i_{\texttt{\$}}]$ with the
aim to form a cycle. _Right_ : To obtain this cycle we additionally need to
swap $\mathsf{BWT}[p]$ with the elements of the dashed rectangle (  )
corresponding to the interval $\mathcal{I}$ having the same height as the
dotted rectangle (  ) covering
$\mathsf{BWT}[i_{\texttt{f}}+1\mathbin{{.}\,{.}}{}i_{\texttt{\$}}-1]$.  Figure
5: Computing $\mathsf{BBWT}$ from $\mathsf{BWT}$ (cf. Sect. 5.4) of our
running example $T=\texttt{bacabbabb{}\$}$. In the _left_ column, we find the
first Lyndon factor $T_{1}=\texttt{b}$ of $T$ by forward steps with
$\mathsf{FL}$. Since $|T_{1}|=1$, $p=i_{\texttt{\$}}$. We obtain the _middle_
column by exchanging $\mathsf{BWT}[4]$ with $\mathsf{BWT}[7]=\texttt{\$}$.
Since there are two b’s between b at $\mathsf{BWT}[4]$ and $ in the _left_
column, we need to swap $\mathsf{BWT}[p]$ with the two elements below of it in
the _middle_ column. This gives a cycle in the _right_ column. We can recurse
since the $\mathsf{FL}$ mapping of $ now yields the second character of $T$.
Figure 6: Special case for computing $\mathsf{BWT}$ from $\mathsf{BBWT}$ (cf.
Sect. 5.4) with the different example string
$T\texttt{\$}:=\texttt{cedabedad\$}$ having $T_{1}=\texttt{ced}$ as its first
Lyndon factor. _Left column_ : We find the first Lyndon factor
$T_{1}=\texttt{ced}$ of $T$ by forward steps with $\mathsf{FL}$. Its last
character is stored at $\mathsf{BWT}[2]$. By exchanging $ with the last
character of $T_{1}$ in $\mathsf{BWT}$, we obtain the middle column. _Middle
column_ : The $\mathsf{LF}$ mapping for the third d in $\mathsf{F}$ becomes
invalid. However, there is only a character run of
$T_{1}[|T_{1}|-1]=\texttt{e}$ in $\mathsf{BWT}{}$ of the
$T_{1}[|T_{1}|]=\texttt{d}$ interval $[7\mathbin{{.}\,{.}}{}8]$ in
$\mathsf{F}$ starting with $p=7$. So we recurse on $\mathsf{LF}[p]$ to find
characters different from $T_{1}[|T_{1}|-2]=\texttt{c}$ to swap in the
respective $T_{1}[|T_{1}|-1]=\texttt{e}$ interval $[9\mathbin{{.}\,{.}}{}10]$.
_Right Column_ : We have created a cycle with the characters of the first
Lyndon factor. A forward step at $ gives the first character of the next
Lyndon factor.

Our aim is to change $\mathsf{BWT}$ such that a forward or backward step
within the characters belonging to $T_{1}$ always results in a cycle.
Informally, we want to cut $T_{1}$ out of $\mathsf{BWT}$, which additionally
allows us to recursively continue with the $\mathsf{FL}$ mapping to find the
end of the next Lyndon factor $T_{2}$.444As a matter of fact, if we now want
to restore the text with the modified $\mathsf{BWT}$ by $\mathsf{LF}$, we
would only produce $T_{2}\cdots T_{t}$. For that, we exchange
$\mathsf{BWT}[i_{\texttt{\$}}]$ with $\mathsf{BWT}[i_{\texttt{f}}]$ (cf. Fig.
5). Then the character $T[{\textrm{{e}}}(T_{1})+1]$ (i.e., the first character
of $T_{2}$) becomes the next character of $ in terms of the forward step
($\mathsf{BWT}[\mathsf{FL}[i_{\texttt{f}}]]=T[{\textrm{{b}}}(T_{2})]$), while
a backwards search on the first character of $T_{1}$ yields $T_{1}$’s last
character ($\mathsf{LF}$ returns $i_{\texttt{\$}}$, but now
$\mathsf{BWT}[i_{\texttt{\$}}]=T_{1}[|T_{1}|]=\texttt{f}$). This is sufficient
as long as $\mathsf{BWT}[i]\not=\texttt{f}$ for every
$i\in(i_{\texttt{f}}\mathbin{{.}\,{.}}{}i_{\texttt{\$}}]$. Otherwise, it can
happen that we change the mapping from the $i$-th f of $\mathsf{F}$ to the
$i$-th f of $\mathsf{BWT}$ (or vice versa) unintentionally. In such a case, we
swap some entries in $\mathsf{BWT}$ within the f interval of $\mathsf{F}$. In
detail, we conduct the exchange ($\mathsf{BWT}[i_{\texttt{\$}}]$ with
$\mathsf{BWT}[i_{\texttt{f}}]$), but continue with swapping $\mathsf{BWT}[i]$
and $\mathsf{BWT}[i+1]$ unless $\mathsf{BWT}[\mathsf{FL}[i]]$ becomes that f
that corresponds to $T_{1}[|T_{1}|]$ for increasing $i$ starting with $i=p$
until $\mathsf{F}[i]\not=\texttt{f}$ or
$\mathsf{LF}[i]\not\in[i_{\texttt{f}}\mathbin{{.}\,{.}}{}i_{\texttt{\$}}]$.
This may not be sufficient if the characters we swap are identical (cf. Fig.
6). In such a case, we recurse on the $T_{1}[|T_{1}|-1]$ interval of
$\mathsf{F}$, see also Algorithm 7 in the appendix.

Instead of checking whether we have created a cycle after each swap, we want
to compute the exact number of swaps needed for this task. For that we note
that exchanging $\mathsf{BWT}[i_{\texttt{\$}}]$ with
$\mathsf{BWT}[i_{\texttt{f}}]$ decrements the values of
$\mathsf{BWT}.{\textrm{{rank}}}_{\texttt{f}}(j)$ for every
$j\in[i_{\texttt{f}}\mathbin{{.}\,{.}}{}i_{\texttt{\$}}]$ by one. In
particular, $\mathsf{BWT}.{\textrm{{select}}}_{\texttt{f}}$ changes for those
f’s in $\mathsf{BWT}$ that are between $i_{\texttt{f}}$ and $i_{\texttt{\$}}$.
Hence, the number of swaps $m$ is the number of positions
$k\in[i_{\texttt{f}}+1\mathbin{{.}\,{.}}{}i_{\texttt{\$}}-1]$ with
$\mathsf{BWT}[k]=\texttt{f}$. The swaps are performed within the range
$\mathcal{I}$ starting with $p+1$ and covering all positions $i$ with
$\mathsf{LF}[i]\in[i_{\texttt{i}}\mathbin{{.}\,{.}}{}i_{\texttt{\$}}]$ and
$\mathsf{F}[i]=\texttt{f}$ since $\mathcal{I}$ covers all entries whose
mapping has changed. However, if $\mathsf{BWT}[p\mathbin{{.}\,{.}}{}]$ starts
with a character run of $T[{\textrm{{e}}}(T_{1})-1]$ (or of
$T[{\textrm{{b}}}(T_{1})]$ if $|T_{1}|=1$)555For $|T_{1}|=1$,
$p=i_{\texttt{\$}}$, and hence, $\mathsf{BWT}[p]$ was $ but now is
$\texttt{f}=T_{1}[|T_{1}|]=T_{1}[1]$., swapping the identical characters does
not change $\mathsf{BWT}$, and therefore has no effect of changing
$\mathsf{LF}$. Instead, we search the end of this run within $\mathcal{I}$ to
swap the first entry $i$ below this run with the first entry of this run, and
recurse on swapping entry $i$ with entries below of it.

#### Correctness.

To see why the swaps restore the LF mapping for $T_{1}$ and the remaining part
of the text $T_{2}\cdots T_{t}$, we examine those substrings of $T$ that we
might no longer find with the LF mapping after exchanging
$\mathsf{BWT}[i_{\texttt{\$}}]$ with $\mathsf{BWT}[i_{\texttt{f}}]$.

In detail, we examine each substring
$S_{j}:=x_{j}y_{j}\texttt{f}\in\Sigma^{3}$ with $j\in[1\mathbin{{.}\,{.}}{}m]$
that is represented in $\mathsf{BWT}$ (before changing it) with
$\mathsf{BWT}[p+j]=y_{j},\mathsf{BWT}[\mathsf{LF}[p+j]]=x_{j},\mathsf{BWT}[\mathsf{FL}[p+j]]=\texttt{f}$,
and
$i_{j}:=\mathsf{FL}[p+j]\in[i_{\texttt{f}}+1\mathbin{{.}\,{.}}{}i_{\texttt{\$}}-1]$.
Due to the LF-mapping,
$\mathsf{BWT}.{\textrm{{select}}}_{\texttt{f}}(\mathsf{BWT}.{\textrm{{rank}}}_{\texttt{f}}(i_{\texttt{f}})+j)=i_{j}$,
meaning that $\mathsf{BWT}[i_{j}]$ is the $j$-th f in
$\mathsf{BBWT}[i_{\texttt{f}}+1\mathbin{{.}\,{.}}{}i_{\texttt{\$}}-1]$, which
stores $m$ f’s. After exchanging $\mathsf{BWT}[i_{\texttt{\$}}]$ with
$\mathsf{BWT}[i_{\texttt{f}}]$, $\mathsf{FL}[p+j]$ becomes $i_{j+1}$ for
$j\in[0\mathbin{{.}\,{.}}{}m]$ with $i_{m+1}:=i_{\texttt{\$}}$. However, for
all $i>p+m$, $\mathsf{FL}[i]$ did not change. Hence, we only have to focus on
the range $\mathcal{I}=[p+1\mathbin{{.}\,{.}}{}p+m]$.

First, suppose that $y_{1}=\mathsf{BWT}[p+1]\not=\mathsf{BWT}[p]$. If we swap
$\mathsf{BWT}[p]$ with $\mathsf{BWT}[p+1]$, then $\mathsf{LF}[p]$ is still
$i_{1}$, but $\mathsf{BWT}[\mathsf{LF}[p]]$ becomes $x_{1}$ such that we have
fixed the substring $x_{1}y_{1}\texttt{f}$. This also works in a more general
setting: If $y_{j}=\mathsf{BWT}[p+j]\not=\mathsf{BWT}[p]$ for every
$j\in[1\mathbin{{.}\,{.}}{}m]$, we can perform $m$ swaps like above for all
$m$ entries in $\mathsf{BWT}[\mathcal{I}]$ to fix all substrings $S_{j}$.

Now suppose that $y_{j}=\mathsf{BWT}[p+j]=\mathsf{BWT}[p]$ for
$j\in[1\mathbin{{.}\,{.}}{}\ell]$ with the largest possible
$\ell\in[2\mathbin{{.}\,{.}}{}m]$. Let $k>p+\ell$ be the first entry with
$\mathsf{BWT}[k]\not=\mathsf{BWT}[p]$. First, suppose that $k\in\mathcal{I}$.
Then $\mathsf{F}[k]=\texttt{f}$, and swapping $\mathsf{BWT}[k]$ with
$\mathsf{BWT}[p]$ restores the LF mapping for the substrings $S_{j}$ with
$j\in[1\mathbin{{.}\,{.}}{}\ell]$ since this swap decrements
$\mathsf{BWT}.{\textrm{{rank}}}_{y_{j}}[p+j]$ by one for every
$j\in[1\mathbin{{.}\,{.}}{}\ell]$. We recurse on swapping $\mathsf{BWT}[k]$
with the following $\mathsf{BBWT}$ entries in $\mathcal{I}$ until all $m$
substrings got restored. Finally, if $k\geq p+m$, then all $y_{i}$ are equal
such that we can find the $x_{i}$ in $\mathsf{BWT}$ consecutively stored at
positions with an $\mathsf{F}$ value of $y_{i}$. Thus, we can apply the swaps
there recursively.

#### Time Complexity.

Fixing a Lyndon factor $T_{x}$, we spend
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}(|\mathcal{I}|)$ time for the swaps
in $\mathsf{BWT}[\mathcal{I}]$, and perform the swaps recursively at most
$|T_{x}|$ times, where we need additionally
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}(n)$ time per recursion step for
computing $\mathsf{LF}[p]$, summing up to
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}(|T_{x}|(|\mathcal{I}|+n))=\mathop{}\mathopen{}\mathcal{O}\mathopen{}(n|T_{x}|)$
time. Since $\sum_{x=1}^{t}|T_{x}|=n$, we yield
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}(n^{2})$ total time.

##  6 Open Problems

Our algorithm of Sect. 5.3 converts $\mathsf{BBWT}$ to $\mathsf{BWT}$, Lyndon
factor by Lyndon factor. It would be interesting to find another conversion
that works character-wise. Here, our inversion algorithm extracts a Lyndon
factor in text order from $\mathsf{BBWT}$, while the used BWT construction
algorithm parses the text in reverse text order.

Crochemore et al. [9, Sect. 4] proposed a space and time trade-off algorithm
based on their in-place techniques computing or inverting $\mathsf{BWT}$. We
are positive that it should be possible to adapt their techniques for
computing or inverting $\mathsf{BBWT}$ or $\mathsf{BWT}^{\circ}$ with a trade-
off parameter.

From the combinatorial perspective, we question whether the number of distinct
Lyndon words of $T$ is bounded by the runs in $\mathsf{BBWT}$. If we can
affirm this question, it would be possible to adapt the $\mathsf{BBWT}$ based
index data structure [3] for $\mathsf{RLBBWT}$ using
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}(r_{\mathsf{BBWT}}{}\lg n)$ bits of
space because this solution needs a bit vector with rank and select support
marking the positions in $\mathsf{BBWT}$ corresponding to the distinct Lyndon
factors. If this number is at most the number of runs $r_{\mathsf{BBWT}}$,
then we can store this bit vector entropy-compressed in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}(r\lg n)$ bits when
$r_{\mathsf{BBWT}}=\mathop{}\mathopen{}o\mathopen{}(n)$ since
$nH_{0}(r)=n\lg(n/(n-r))+r\lg((n-r)/r)\leq n\lg r\Leftrightarrow
r\lg((n-r)/r)\leq n\lg(r(n-r)/n)$ for $r=r_{\mathsf{BBWT}}$.

Speaking of $\mathsf{RLBBWT}$, we wonder whether we can construct
$\mathsf{RLBBWT}$ online in run-length compressed space similar to Cor. 4.2.
With the run-length compressed wavelet tree, the algorithm of Bonomo et al.
[5, Thm. 17] works in $\mathop{}\mathopen{}\mathcal{O}\mathopen{}(n\lg
r_{\mathsf{BBWT}}/\lg\lg r_{\mathsf{BBWT}})$ time with
$\max_{x\in[1\mathbin{{.}\,{.}}{}t]}|T_{x}|+\mathop{}\mathopen{}\mathcal{O}\mathopen{}(r_{\mathsf{BBWT}}\lg
n)$ bits of space by reading each Lyndon factor of the text individually.

## References

  * [1] Donald Adjeroh, Timothy Bell, and Amar Mukherjee.  The Burrows-Wheeler Transform:: Data Compression, Suffix Arrays, and Pattern Matching.  Springer, 2008.
  * [2] Hideo Bannai, Juha Kärkkäinen, Dominik Köppl, and Marcin Piatkowski.  Constructing the bijective BWT.  ArXiv 1911.06985, 2019.
  * [3] Hideo Bannai, Juha Kärkkäinen, Dominik Köppl, and Marcin Piatkowski.  Indexing the bijective BWT.  In Proc. CPM, volume 128 of LIPIcs, pages 17:1–17:14, 2019\.
  * [4] Philip Bille, Anders Roy Christiansen, Patrick Hagge Cording, Inge Li Gørtz, Frederik Rye Skjoldjensen, Hjalte Wedel Vildhøj, and Søren Vind.  Dynamic relative compression, dynamic partial sums, and substring concatenation.  Algorithmica, 80(11):3207–3224, 2018.
  * [5] Silvia Bonomo, Sabrina Mantaci, Antonio Restivo, Giovanna Rosone, and Marinella Sciortino.  Sorting conjugates and suffixes of words in a multiset.  Int. J. Found. Comput. Sci., 25(8):1161, 2014.
  * [6] Michael Burrows and David J. Wheeler.  A block sorting lossless data compression algorithm.  Technical Report 124, Digital Equipment Corporation, Palo Alto, California, 1994.
  * [7] Timothy M. Chan, J. Ian Munro, and Venkatesh Raman.  Selection and sorting in the “restore” model.  ACM Trans. Algorithms, 14(2):11:1–11:18, 2018.
  * [8] Kuo Tsai Chen, Ralph H. Fox, and Roger C. Lyndon.  Free differential calculus, IV. The quotient groups of the lower central series.  Annals of Mathematics, pages 81–95, 1958.
  * [9] Maxime Crochemore, Roberto Grossi, Juha Kärkkäinen, and Gad M. Landau.  Computing the Burrows-Wheeler transform in place and in small space.  J. Discrete Algorithms, 32:44–52, 2015.
  * [10] Jean-Pierre Duval.  Factorizing words over an ordered alphabet.  J. Algorithms, 4(4):363–381, 1983.
  * [11] Paolo Ferragina and Giovanni Manzini.  Opportunistic data structures with applications.  In Proc. FOCS, pages 390–398, 2000.
  * [12] Paolo Ferragina, Giovanni Manzini, and S. Muthu Muthukrishnan.  The Burrows-Wheeler Transform: Ten Years Later.  DIMACS, 2004.
  * [13] Michael L. Fredman and Dan E. Willard.  Surpassing the information theoretic bound with fusion trees.  J. Comput. Syst. Sci., 47(3):424–436, 1993.
  * [14] Travis Gagie, Giovanni Manzini, Gonzalo Navarro, and Jens Stoye.  25 Years of the Burrows-Wheeler Transform (Dagstuhl Seminar 19241).  Dagstuhl Reports, 9(6):55–68, 2019.
  * [15] Raffaele Giancarlo, Antonio Restivo, and Marinella Sciortino.  From first principles to the Burrows and Wheeler transform and beyond, via combinatorial optimization.  Theor. Comput. Sci., 387(3):236–248, 2007.
  * [16] Joseph Yossi Gil and David Allen Scott.  A bijective string sorting transform.  ArXiv 1201.3077, 2012.
  * [17] Roberto Grossi, Ankur Gupta, and Jeffrey Scott Vitter.  High-order entropy-compressed text indexes.  In Proc. SODA, pages 841–850, 2003.
  * [18] Torben Hagerup.  Fast deterministic construction of static dictionaries.  In Proc. SODA, pages 414–418, 1999.
  * [19] Wing-Kai Hon, Tsung-Han Ku, Chen-Hua Lu, Rahul Shah, and Sharma V. Thankachan.  Efficient algorithm for circular Burrows-Wheeler transform.  In Proc. CPM, volume 7354 of LNCS, pages 257–268, 2012.
  * [20] R. C. Lyndon.  On Burnside’s problem.  Transactions of the American Mathematical Society, 77(2):202–215, 1954.
  * [21] Veli Mäkinen and Gonzalo Navarro.  Succinct suffix arrays based on run-length encoding.  Nord. J. Comput., 12(1):40–66, 2005.
  * [22] Udi Manber and Eugene W. Myers.  Suffix arrays: A new method for on-line string searches.  SIAM J. Comput., 22(5):935–948, 1993.
  * [23] Sabrina Mantaci, Antonio Restivo, Giovanna Rosone, and Marinella Sciortino.  An extension of the Burrows-Wheeler transform.  Theor. Comput. Sci., 387(3):298–312, 2007.
  * [24] Sabrina Mantaci, Antonio Restivo, Giovanna Rosone, and Marinella Sciortino.  Suffix array and Lyndon factorization of a text.  J. Discrete Algorithms, 28:2–8, 2014.
  * [25] Sabrina Mantaci, Antonio Restivo, and Marinella Sciortino.  Burrows-Wheeler transform and Sturmian words.  Inf. Process. Lett., 86(5):241–246, 2003.
  * [26] J. Ian Munro and Venkatesh Raman.  Selection from read-only memory and sorting with minimum data movement.  Theor. Comput. Sci., 165(2):311–323, 1996.
  * [27] Gonzalo Navarro and Yakov Nekrich.  Optimal dynamic sequence representations.  SIAM J. Comput., 43(5):1781–1806, 2014.
  * [28] Ge Nong, Sen Zhang, and Wai Hong Chan.  Two efficient algorithms for linear time suffix array construction.  IEEE Trans. Computers, 60(10):1471–1484, 2011.
  * [29] Tatsuya Ohno, Yoshimasa Takabatake, Tomohiro I, and Hiroshi Sakamoto.  A faster implementation of online run-length Burrows-Wheeler transform.  In Proc. IWOCA, volume 10765 of LNCS, pages 409–419, 2017\.
  * [30] Alberto Policriti and Nicola Prezza.  LZ77 computation based on the run-length encoded BWT.  Algorithmica, 80(7):1986–2011, 2018.

##  Appendix A Computing the Transforms

For readers unfamiliar with the three studied BWT variants introduced in Sect.
3.3, we provide didactically simplified constructions in Figs. 7, 8 and 9 that
neglect the in-place restriction.

Figure 7: Constructing $\mathsf{BBWT}$ of
$T\texttt{\$}=\texttt{bacabbabb}\texttt{\$}$. The Lyndon factorization of
$T\texttt{\$}$ is visualized by the vertical bars. We take all conjugates of
each Lyndon factor into a list, sort this list with respect to the
$\prec_{\omega}$ order. The first characters and the last characters in this
list give $\mathsf{F}$ and $\mathsf{BBWT}$, respectively.  Figure 8:
Constructing $\mathsf{BWT}$ of $\texttt{\$}T=\texttt{\$}\texttt{bacabbabb}$.
Since $\texttt{\$}T$ is a Lyndon word,
$\mathsf{BWT}_{\texttt{\$}T}=\mathsf{BBWT}_{\texttt{\$}T}$. To construct
$\mathsf{BWT}$, we follow Fig. 7: The Lyndon factorization of $\texttt{\$}T$
consists only of $\texttt{\$}T$ itself. Consequently, we take all conjugates
of $\texttt{\$}T$ (_left_) and sort them (_right_). Thanks to the $, it does
not matter whether we sort by lexicographic order or $\prec_{\omega}$ order
[5, Lemma 7]. The first characters and the last characters in this sorted list
give $\mathsf{F}$ and $\mathsf{BWT}$, respectively.  Figure 9: Computing
$\mathsf{BWT}^{\circ}$ of $T=\texttt{bacabbabb}$. Since $T$ is primitive, it
has a Lyndon conjugate, which is . To construct $\mathsf{BWT}^{\circ}$, we
follow Fig. 7: We take all conjugates of (_left_), and sort them
lexicographically (_right_). Here, the lexicographic order is equivalent to
the $\prec_{\omega}$ order [5, Lemma 7]. The first characters and the last
characters in this list give $\mathsf{F}$ and $\mathsf{BWT}^{\circ}$,
respectively.

##  Appendix B From Run-Length Compressed Text to $\mathsf{RLBWT}$

Complementary to the study of Sect. 4, we want to examine how much space is
needed to compute $\mathsf{RLBWT}$ in $r_{\mathsf{BWT}}\lg\sigma$ bits
(without a wavelet tree) having the text also run-length compressed. For that,
we use the algorithm of Crochemore et al. [9, Fig. 2] to compute the
$\mathsf{RLBWT}$ in-place in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}(n^{2})$ online on the reversed
text.

######  Lemma B.1.

Given that $r_{T}$ is the number of character runs in the run-length
compressed text $T$, we can compute $\mathsf{RLBWT}$ in
$\mathop{}\mathopen{}\mathcal{O}\mathopen{}(n^{2})$ time with
$r_{\mathsf{BWT}}+r_{T}/2+\mathop{}\mathopen{}\mathcal{O}\mathopen{}(1)$ words
of working space, including the space of the run-length compressed text and
$\mathsf{RLBWT}$.

######  Proof B.2.

Suppose $\texttt{b}:=T[i]=\cdots=T[k]$ is a character run. Then adding this
character run to $\mathsf{RLBWT}$ induces at most two character runs in
$\mathsf{BWT}$. That is because (1) the context of $T[k]$ (i.e., the suffix
$T[k+1\mathbin{{.}\,{.}}{}]$ succeeding $T[k]$) starting with $T[k+1]\cdots$
can be arbitrary, but (2) the context of $T[j]$ starts always with one or
multiple b’s, for $j\in[i\mathbin{{.}\,{.}}{}k)$. Hence, adding a character
run of $T$ to $\mathsf{BWT}$ can cause at most two new character runs in
$\mathsf{BWT}$. Consequently, it is possible that the run-length BWT computed
on at least half of character runs of the text already needs as much space as
$\mathsf{RLBWT}_{T}$. In total, the memory peak is at most
$r_{\mathsf{BWT}}+r_{T}/2$ words, since we freed up at least half of character
runs of $T$ when reaching this peak.

##  Appendix C Pseudo Codes

1 task: output the ending positions of all Lyndon factors

$k\leftarrow 0$

$\triangleright$ ending position of first Lyndon factor

2 while  _k < n_ do

3 $i\leftarrow k+1$ and $j\leftarrow k+2$

4 while  _$j\not=n+1$ and $T[i]\leq T[j]$_ do

5 if  _$T[i] <T[j]$_ then $i\leftarrow k+1$

6 $\triangleright$ $T[k+1\mathbin{{.}\,{.}}{}j]$ is a Lyndon word if
_$T[i]=T[j]$_ then $i\leftarrow i+1$

7 $\triangleright$
$T[k+1\mathbin{{.}\,{.}}{}i]=T[j-(i-k)\mathbin{{.}\,{.}}{}j]$ $j\leftarrow
j+1$

8

9 repeat $\triangleright$ invariant: $T[i]>T[j]$ or $j=n+1$

10 $k\leftarrow k+(j-i)$

11 output $k$

12 until  _$k\geq i$_

Algorithm 1 Duval’s Algorithm, see Lemma 3.1 and [10, Algo. 2.1]

1 foreach  _Lyndon factor $F_{x}$ with $x=1$ up to $t$_ do

2 prepend $T_{x}[|T_{x}|]$ to $\mathsf{BBWT}$

$p\leftarrow 1$

$\triangleright$ insert position in $\mathsf{BBWT}$

3 for  _$i=|T_{x}|-1$ down to $1$_ do

4 $p\leftarrow\mathsf{LF}[p]+1$

5 insert $T_{x}[i]$ right after $\mathsf{BBWT}[p-1]$ such that
$\mathsf{BBWT}[p]=T_{x}[i]$

6

Algorithm 2 Computing $\mathsf{BBWT}$ from $T$ [5, Algo. 13], cf. Sect. 5.1

1

1 function  _$C(\mathsf{BWT},c)$_ :

2 $\mathit{count}\leftarrow 0$;

3 for  _$j=1$ up to $|\mathsf{BWT}|$_ do

4 if  _$\mathsf{BWT}[j] <c$_ then

5 $\mathit{count}\leftarrow\mathit{count}+1$

6

7

8 return $\mathit{count}$

9

10

1 function  _${\textrm{{rank}}}(\mathsf{BWT},c)$_ :

2 $\mathit{rank}\leftarrow 0$

3 for  _$j=1$ up to $|\mathsf{BWT}|$_ do

4 if  _$\mathsf{BWT}[j]=c$_ then

5 $\mathit{rank}\leftarrow\mathit{rank}+1$

6

7

8 return $\mathit{rank}$

9

Algorithm 3 Functions for computing
$\mathsf{LF}[i]=C(\mathsf{BWT},\mathsf{BWT}[i])+{\textrm{{rank}}}(\mathsf{BWT}[1\mathbin{{.}\,{.}}{}i],\mathsf{BWT}[i])$,
cf. Eq. 2

1 let $\tilde{T}[1\mathbin{{.}\,{.}}{}n]$ denote the working space of
$n\lg\sigma$ bits storing $T[1\mathbin{{.}\,{.}}{}n]$

swap $\tilde{T}[n]$ with $\tilde{T}[n-1]$

$\triangleright$
$\mathsf{BWT}_{T[n-1\mathbin{{.}\,{.}}{}n]}=\tilde{T}[n-1\mathbin{{.}\,{.}}{}n]$
since $T$ is Lyndon

$\mathit{lastchar}\leftarrow\tilde{T}[n]$

$\triangleright$ the character most recently inserted into
$\mathsf{BWT}^{\circ}$

$\mathit{lastpos}\leftarrow n$

$\triangleright$ the position of $\mathit{lastchar}$ in $\tilde{T}$

2 for  _$i=n-1$ down to $2$_ do $\triangleright$
$\tilde{T}[1\mathbin{{.}\,{.}}{}i-1]=T[1\mathbin{{.}\,{.}}{}i-1]$ and
$\tilde{T}[i\mathbin{{.}\,{.}}{}n]=\mathsf{BWT}^{\circ}[i\mathbin{{.}\,{.}}{}n]$

3 $\mathit{lastpos}\leftarrow
i+C(\tilde{T}[i\mathbin{{.}\,{.}}{}n],\mathit{lastchar})+{\textrm{{rank}}}(\tilde{T}[i\mathbin{{.}\,{.}}{}\mathit{lastpos}],\mathit{lastchar})$

$\triangleright$ apply Algorithm 3 for $\mathit{lastpos}\leftarrow
i+\mathsf{LF}[\mathit{lastpos}-i]$ with
$\mathsf{BWT}[k]=\tilde{T}[k+i]\leavevmode\nobreak\ \forall k$

4

$\mathit{lastchar}\leftarrow\tilde{T}[i-1]=T[i-1]$

$\triangleright$ save $\tilde{T}[i-1]$ before overwriting it.

5 for  _$j=i-1$ to $\mathit{lastpos}$_ do
$\tilde{T}[j]\leftarrow\tilde{T}[j+1]$

6 $\tilde{T}[\mathit{lastpos}]\leftarrow\mathit{lastchar}$

return $\tilde{T}=\mathsf{BWT}^{\circ}$

Algorithm 4 Computing $\mathsf{BWT}^{\circ}$ in-place for a Lyndon word $T$,
cf. Sect. 5.1

1 $p\leftarrow$ the position of $T[1]$ in $\mathsf{BWT}^{\circ}{}$

2 $T\leftarrow$ empty string

3 while  _$|\mathsf{BWT}^{\circ}| >1$_ do $\triangleright$ apply [9, Fig. 3]

4 $p^{\prime}\leftarrow\mathsf{FL}[p]$

5 append $\mathsf{BWT}^{\circ}[p^{\prime}]$ to $T$

6 $\mathsf{BWT}^{\circ}[p^{\prime}]\leftarrow\texttt{\$}$

7 delete $\mathsf{BWT}^{\circ}[p]$

8 $p\leftarrow p^{\prime}$

9

10return $T$

Algorithm 5 Inverting $\mathsf{BWT}^{\circ}$, cf. Sect. 5.2

1 $T\leftarrow$ empty string

2 while  _$\mathsf{BBWT}$ is not empty_ do $\triangleright$ extract the
currently last Lyndon factor

3 insert $ after $\mathsf{BBWT}[1]$ such that $\mathsf{BBWT}[2]=\texttt{\$}$

$p\leftarrow 2$

$\triangleright$ $p$ is the position where $ is stored

4

5 while  _$p\not=1$_ do $\triangleright$ apply Algorithm 5

6 $p^{\prime}\leftarrow\mathsf{FL}[p]$

7 append $\mathsf{BBWT}[p^{\prime}]$ to the text buffer

8 $\mathsf{BBWT}[p^{\prime}]\leftarrow\texttt{\$}$

9 delete $\mathsf{BWT}[p]$

10 $p\leftarrow p^{\prime}$

11

delete $\mathsf{BBWT}[1]$

$\triangleright$ $p=1$ and $\mathsf{F}[1]=\mathsf{BBWT}[1]=\texttt{\$}$

12

13prepend the text buffer to already restored text $T$

14 return $T$

Algorithm 6 Inverting $\mathsf{BBWT}$, cf. Sect. 5.3

$x\leftarrow 1$

$\triangleright$ counts the currently processed Lyndon factor
$T_{x},x\in[1\mathbin{{.}\,{.}}{}t]$

1

2while  _$\mathsf{LF}[i_{\texttt{\$}}]\not=\texttt{\$}$ where
$i_{\texttt{\$}}$ is the position of $ in $\mathsf{BWT}$_ do $\triangleright$
$\mathsf{BWT}[\mathsf{FL}[i_{\texttt{\$}}]]=T_{x}[1]$

$p\leftarrow\mathsf{FL}^{(|T_{x}|-1)}[i_{\texttt{\$}}]$

$\triangleright$ apply $\mathsf{FL}$ $(|T_{x}|-1)$ times

stipulate that $T_{x}[0]:=\texttt{\$}$

$\triangleright$ $\mathsf{BWT}[p]=T_{x}[|T_{x}|-1]$ even for $|T_{x}|=1$

$i_{\texttt{f}}\leftarrow\mathsf{FL}[p]$

$\triangleright$
$\mathsf{F}[p]=T_{x}[|T_{x}|],\mathsf{BWT}[i_{\texttt{f}}]=T_{x}[|T_{x}|]$

3 exchange $\mathsf{BWT}[i_{\texttt{f}}]$ with $\mathsf{BWT}[i_{\texttt{\$}}]$

4
$m\leftarrow\left|\\{i\in[i_{\texttt{f}}+1\mathbin{{.}\,{.}}{}i_{\texttt{\$}}-1]\text{\leavevmode\nobreak\
with\leavevmode\nobreak\ }\mathsf{BWT}[i]=T_{x}[|T_{x}|]\\}\right|$

$0pt\leftarrow 0$

$\triangleright$ recursion depth for the swaps

$p^{\prime}\leftarrow\mathsf{LF}[p]$

$\triangleright$ save $\mathsf{LF}[p]$ for the recursion

5 while  _$m >0$_ do

$\mathrm{dst}\leftarrow p,\mathrm{src}\leftarrow p+1$ $\triangleright$ try to
swap $\mathsf{BWT}[\mathrm{dst}]$ with next unequal entry

6 while  _$\mathsf{BWT}[\mathrm{src}]=T_{x}[|T_{x}|-0pt-1]$_ do
$\mathrm{src}\leftarrow\mathrm{src}+1$

7 if  _$\mathsf{F}[\mathrm{src}]=T_{x}[|T_{x}|-0pt]$ and $\mathrm{src}\leq
p+m$_ then

8 swap $\mathsf{BWT}[\mathrm{src}]$ with $\mathsf{BWT}[\mathrm{dst}]$

9 $\mathrm{dst}\leftarrow\mathrm{src}$, $m\leftarrow
m-(\mathrm{src}-\mathrm{dst})$

$p^{\prime}\leftarrow p^{\prime}+(\mathrm{src}+\mathrm{dst}-1)$

$\triangleright$ move $p^{\prime}$ such that $\mathsf{FL}[p^{\prime}]=p$

10 goto Line 7

11

12 increment $0pt$ by one, $p\leftarrow p^{\prime}$,
$p^{\prime}\leftarrow\mathsf{LF}[p^{\prime}]$

13

14 $x\leftarrow x+1$ $\triangleright$ done with $T_{1}\cdots T_{x-1}$

15invariant: $x=t$

Algorithm 7 Converting $\mathsf{BWT}$ to $\mathsf{BBWT}$ in-place, cf. Sect.
5.4


$\displaystyle\frac{\delta^{2}S^{+-}_{2}(z,w)}{\delta\mathcal{B}_{+}(x)\delta\mathcal{B}_{-}(y)}$
$\displaystyle=$
$\displaystyle-\frac{1}{2\kappa^{2}}\left[\partial_{i}^{2}\,\partial_{j}\right]_{w}\left[\partial_{i}^{2}\,\partial_{k}\right]_{z}G_{0\,-j+k}(w,z)$
(C.15) $\displaystyle\int ds^{-}\,f(s^{-},w^{-})\int
dt^{+}\,f(t^{+},z^{+})\,\delta(x^{+}-w^{+})\delta(y^{-}-z^{-})\delta^{2}(x_{\bot}-w_{\bot})\delta^{2}(y_{\bot}-z_{\bot})\,.$
(C.16)

The vertices determine the structure of the one-loop correction to the
propagator.

The kernel of the correction is defined through the simple variations:

$2\,\imath\,S_{xy\,1}=\left(\frac{\delta^{2}\,Sp\ln(G)}{\delta\mathcal{B}_{+x}\,\delta\mathcal{B}_{-y}}\right)_{\mathcal{B}_{\pm}=0}=\frac{\delta^{2}\,G_{+-}(z,z_{1})}{\delta\mathcal{B}_{+x}\,\delta\mathcal{B}_{-y}}\,G_{+-}^{-1}(z_{1},z)-\frac{\delta\,G_{+-}(z,z_{1})}{\delta\mathcal{B}_{-y}}\,G_{+-}^{-1}(z_{1},z_{2})\,\frac{\delta\,G_{+-}(z_{2},z_{3})}{\delta\mathcal{B}_{+x}}\,G_{+-}^{-1}(z_{3},z)$
(C.17)

with Green’s function given by Eq. (C) expression. We have then for the first
term in the expression:

$\displaystyle 2\,\imath\,S_{xy\,1\,1}\,$ $\displaystyle=$
$\displaystyle\,\frac{\delta^{2}\,G_{+-}(z,z_{1})}{\delta\mathcal{B}_{+x}\,\delta\mathcal{B}_{-y}}\,G_{+-}^{-1}(z_{1},z)\,=\,-\,G_{0\,+-}(z,w)\,\frac{\delta^{2}S^{-+}_{2}(w,z)}{\delta\mathcal{B}_{+x}\delta\mathcal{B}_{-y}}\,+\,$
(C.18) $\displaystyle+$ $\displaystyle G_{0\,+-}(z,w)\,\frac{\delta
S^{--}(w,w_{1})}{\delta\mathcal{B}_{+x}}\,G_{0\,-+}(w_{1},w_{2})\,\frac{\delta
S^{++}(w_{2},z)}{\delta\mathcal{B}_{-y}}\,+\,$ $\displaystyle+$ $\displaystyle
G_{0\,+-}(z,w)\,\frac{\delta
S_{1}^{-+}(w,w_{1})}{\delta\mathcal{B}_{+x}}\,G_{0\,+-}(w_{1},w_{2})\,\frac{\delta
S_{1}^{-+}(w_{2},z)}{\delta\mathcal{B}_{-y}}\,+\,$ $\displaystyle+$
$\displaystyle G_{0\,+-}(z,w)\,\frac{\delta
S_{1}^{-+}(w,w_{1})}{\delta\mathcal{B}_{-y}}\,G_{0\,+-}(w_{1},w_{2})\,\frac{\delta
S_{1}^{-+}(w_{2},z)}{\delta\mathcal{B}_{+x}}\,.$

For the second term of Eq. (C.17) we obtain:

$2\,\imath\,S_{xy\,1\,2}\,=\,-\,G_{0\,+-}(z,w)\,\frac{\delta
S_{1}^{-+}(w,w_{1})}{\delta\mathcal{B}_{-y}}\,G_{0\,+-}(w_{1},w_{2})\,\frac{\delta
S_{1}^{-+}(w_{2},z)}{\delta\mathcal{B}_{+x}}\,,$ (C.19)

it cancels with the last term (or term before the last) from the previous
expression. So, the contribution we have are represented by the three first
terms of Eq. (C.18) kernel. We calculate them consequently one by one, the
results we obtained are listed below.

  1. 1.

The first term we have is

$\displaystyle 2$
$\displaystyle\imath\,S_{xy\,1\,1\,1}\,=\,-\,\frac{S^{-+}_{2}(w,z)}{\delta\mathcal{B}_{+x}\delta\mathcal{B}_{-y}}\,G_{0\,+-}(z,w)\,=\,\frac{1}{2\kappa^{2}}\,\int
d^{4}z\,\int
d^{4}w\,\delta(x^{+}-w^{+})\delta(y^{-}-z^{-})\delta^{2}(x_{\bot}-w_{\bot})\delta^{2}(y_{\bot}-z_{\bot})\,$
(C.20)
$\displaystyle\partial_{ix}^{2}\,\partial_{iy}^{2}\,\left(\eta_{jk}\,\partial_{jx}\,\partial_{ky}\right)\,\int
ds^{-}\,f(s^{-},w^{-})\int
dt^{+}\,f(t^{+},z^{+})\,G_{0\,-j+k}(w,z)\,\partial_{ix}^{2}\,\partial_{iy}^{2}\,G_{0\,+-}(t^{+},z^{-},z_{\bot},w^{+},s^{-},w_{\bot})\,=\,$
$\displaystyle=$
$\displaystyle\,\partial_{ix}^{2}\,\partial_{iy}^{2}\,\left(\eta_{jk}\partial_{jx}\,\partial_{ky}\right)\,\int\,dp_{+}\,\frac{1}{p_{+}\,-\,\imath\varepsilon}\,\int
dp_{-}\,\frac{1}{p_{-}\,+\,\imath\varepsilon}\,\int\,\frac{d^{2}p_{\bot}}{(2\pi)^{4}}\,\frac{e^{-\imath\,(p_{i}\,-\,k_{i})(x_{i}\,-\,y_{i})}}{2p_{+}p_{-}\,-\,p_{\bot}^{2}\,+\,\imath\varepsilon}$
$\displaystyle\int\,\frac{d^{2}k_{\bot}}{(2\pi)^{2}}\,\frac{1}{2p_{+}p_{-}\,-\,k_{\bot}^{2}\,+\imath\varepsilon}\,=\,\partial_{ix}^{2}\,\partial_{iy}^{2}\,\left(\eta_{jk}\partial_{jx}\,\partial_{ky}\right)\,\int\,\frac{d^{2}p_{\bot}}{(2\pi)^{4}}\,\int\,\frac{d^{2}k_{\bot}}{(2\pi)^{2}}\,e^{-\imath\,(p_{i}\,-\,k_{i})(x_{i}\,-\,y_{i})}$
$\displaystyle\int
dp_{-}\,\frac{1}{p_{-}\,(4p_{-})^{2}}\,\int\,\frac{dp_{+}}{p_{+}\,-\,\imath\varepsilon}\,\frac{1}{p_{+}\,-\,p_{\bot}^{2}/2p_{-}\,+\imath\varepsilon}\,\frac{1}{p_{+}\,-\,k_{\bot}^{2}/2p_{-}\,+\imath\varepsilon}\,=\,$
$\displaystyle=$
$\displaystyle\frac{\imath}{2\pi}\,\partial_{ix}^{2}\,\partial_{iy}^{2}\,\left(\eta_{jk}\partial_{jx}\,\partial_{ky}\right)\,\int\frac{dp_{-}}{p_{-}}\,\int\,\frac{d^{2}p_{\bot}}{(2\pi)^{2}}\,\int\,\frac{d^{2}k_{\bot}}{(2\pi)^{2}}\,\frac{e^{-\imath\,(p_{i}\,-\,k_{i})(x_{i}\,-\,y_{i})}}{p_{\bot}^{2}\,k_{\bot}^{2}}\,.$

We notice, that except the sign and numericall coefficient, the structure of
the expression is the same as the corresponding term of the Eq. (C) effective
action after it’s variation with respect to the reggeized fields and
substitution of the $<\varepsilon_{-}\,\varepsilon_{+}>$ correlator directly
in the expression., that clear from the QFT calculation principles. This
correspondence helps to check correctness of the obtained answers. We also
note, that the non-zero $\gamma$ coefficient of Eq. (79) expression provides
here an additional $2$ factor. Namely, for $\gamma\,=\,0$ case, which is
Liparov’s [6] result, the overall numerical coefficient in front of Eq. (C.20)
is $1/4$.

  2. 2.

Next term we calculate is

$\displaystyle 2$ $\displaystyle\imath\,S_{xy\,1\,1\,2}\,=\,\frac{\delta
S^{--}(w,w_{1})}{\delta\mathcal{B}_{+x}}\,G_{0\,-+}(w_{1},w_{2})\,\frac{\delta
S^{++}(w_{2},z)}{\delta\mathcal{B}_{-y}}\,G_{0\,+-}(z,w)\,=\,\int dz^{+}\,\int
dw^{+}_{2}\,\int dw^{-}\,\int dw^{+}_{1}\,$ (C.21)
$\displaystyle\frac{1}{4}\,\partial_{i\,x}^{2}\,\partial_{i\,y}^{2}\,\int\frac{d^{2}p_{\bot}}{(2\pi)^{4}}\,\int\frac{d^{2}k_{\bot}}{(2\pi)^{4}}\,\left(p_{i}k_{i}\right)^{2}\,e^{e^{-\imath\,(p_{i}\,-\,k_{i})(x_{i}\,-\,y_{i})}}\,\int\,\frac{dp_{+}dp_{-}}{p^{2}\,+\,\imath\varepsilon}\,\int\,\frac{dk_{+}dk_{-}}{k^{2}\,+\,\imath\varepsilon}\,e^{\imath\,x^{+}\,(p_{+}\,-\,k_{+})\,-\,\imath\,y^{-}\,(p_{-}\,-\,k_{-})}\,$
$\displaystyle\int ds^{-}\,\,f(w^{-}_{1},s^{-})\,f(s^{-},w^{-})\int
ds^{+}\,f(z^{+},s^{+})\,f(s^{+},w^{+}_{2})\,e^{-\,\imath\,p_{+}\,z^{+}}\,e^{\imath\,p_{-}\,w^{-}}\,e^{\imath\,k_{+}\,w^{+}_{2}}\,e^{-\,\imath\,k_{-}\,w^{-}_{1}}\,=\,$
$\displaystyle=$
$\displaystyle\,\frac{1}{4}\,\partial_{i\,x}^{2}\,\partial_{i\,y}^{2}\,\int\frac{d^{2}p_{\bot}}{(2\pi)^{3}}\,\int\frac{d^{2}k_{\bot}}{(2\pi)^{3}}\,\left(p_{i}k_{i}\right)^{2}\,e^{-\imath\,(p_{i}\,-\,k_{i})(x_{i}\,-\,y_{i})}\,\int\,\frac{dp_{+}dp_{-}}{\left(p^{2}\,+\,\imath\varepsilon\right)\,\left(p_{+}\,-\,\imath\varepsilon\right)\,\left(p_{-}\,-\,\imath\varepsilon\right)}\,$
$\displaystyle\int\,\frac{dk_{+}dk_{-}}{\left(k^{2}\,+\,\imath\varepsilon\right)\,\left(k_{+}\,-\,\imath\varepsilon\right)\,\left(k_{-}\,-\,\imath\varepsilon\right)}\,e^{\imath\,x^{+}\,(p_{+}\,-\,k_{+})\,-\,\imath\,y^{-}\,(p_{-}\,-\,k_{-})}\,\delta(p_{+}\,-\,k_{+})\,\delta(p_{-}\,-\,k_{-})\,=\,$
$\displaystyle=$
$\displaystyle\,\frac{1}{4}\,\partial_{i\,x}^{2}\,\partial_{i\,y}^{2}\,\int\frac{d^{2}p_{\bot}}{(2\pi)^{3}}\,\int\frac{d^{2}k_{\bot}}{(2\pi)^{3}}\,\left(p_{i}k_{i}\right)^{2}\,e^{e^{-\imath\,(p_{i}\,-\,k_{i})(x_{i}\,-\,y_{i})}}\,$
$\displaystyle\int\,\frac{dp_{+}dp_{-}}{\left(2p_{+}\,p_{-}\,-\,p_{\bot}^{2}\,+\,\imath\varepsilon\right)\,\left(2p_{+}\,p_{-}\,-\,k_{\bot}^{2}\,+\,\imath\varepsilon\right)}\,\frac{1}{\left(p_{+}\,-\,\imath\varepsilon\right)^{2}\,\left(p_{-}\,-\,\imath\varepsilon\right)^{2}}\,.$

Here we used the $f$ function representation of the following type:

$\int
dz^{+}\,f(z^{+},s^{+})\,e^{-\imath\,p_{+}\,z^{+}}\,=\,\int_{s^{+}}^{\infty}dz^{+}\,e^{-\imath\,(p_{+}\,-\,\imath\varepsilon)\,z^{+}}\,=\,-\,\frac{\imath}{p_{+}\,-\,\imath\varepsilon}\,e^{-\imath\,p_{+}\,s^{+}}\,.$
(C.22)

The resulting positions of the poles in the expression coincide with the
result of [6] results. The integral can be calculated enclosing the
integration contour in the upper or lower parts of the integration plane, the
answers are the same in both cases, the plane we choose is a plane of complex
$p_{+}$ coordinate. We obtain therefore:

$\displaystyle 2$
$\displaystyle\,\imath\,S_{xy\,1\,1\,2}\,=\,\frac{-2\pi\imath}{4}\,\partial_{i\,x}^{2}\,\partial_{i\,y}^{2}\,$
(C.23)
$\displaystyle\int\frac{d^{2}p_{\bot}}{(2\pi)^{3}}\,\int\frac{d^{2}k_{\bot}}{(2\pi)^{3}}\,\left(p_{i}k_{i}\right)^{2}\,e^{e^{-\imath\,(p_{i}\,-\,k_{i})(x_{i}\,-\,y_{i})}}\,\int\,\frac{dp_{-}}{(2p_{-})^{2}\,p_{-}^{2}}\,\left(\frac{(2p_{-})^{3}}{p_{\bot}^{4}\,\left(p_{\bot}^{2}-k_{\bot}^{2}\right)}\,+\,\frac{(2p_{-})^{3}}{k_{\bot}^{4}\,\left(k_{\bot}^{2}-p_{\bot}^{2}\right)}\right)\,=\,$
$\displaystyle=$
$\displaystyle\,\frac{\imath}{4\pi}\,\partial_{i\,x}^{2}\,\partial_{i\,y}^{2}\,\int\frac{dp_{-}}{p_{-}}\,\int\frac{d^{2}p_{\bot}}{(2\pi)^{2}}\,\int\frac{d^{2}k_{\bot}}{(2\pi)^{2}}\,\left(p_{i}k_{i}\right)^{2}\,e^{-\imath\,(p_{i}\,-\,k_{i})(x_{i}\,-\,y_{i})}\,\frac{p_{\bot}^{2}\,+\,k_{\bot}^{2}}{p_{\bot}^{4}\,k_{\bot}^{4}}\,.$

In both answers we used Eq. (135)-Eq. (136) form of the propagators, the
structure of the terms coincides with the amplitude’s expression presented in
[6] paper.

  3. 3.

The last terms we need is the following one:

$\displaystyle 2$
$\displaystyle\imath\,S_{xy\,1\,1\,3}\,=\,G_{0\,+-}(z,w)\,\frac{\delta
S_{1}^{-+}(w,w_{1})}{\delta\mathcal{B}_{+x}}\,G_{0\,+-}(w_{1},w_{2})\,\frac{\delta
S_{1}^{-+}(w_{2},z)}{\delta\mathcal{B}_{-y}}\,=\,\frac{1}{4}\,\partial_{i\,x}^{2}\,\partial_{i\,y}^{2}\,$
$\displaystyle\int\frac{d^{2}p_{\bot}}{(2\pi)^{3}}\,\int\frac{d^{2}k_{\bot}}{(2\pi)^{3}}\,p_{\bot}^{2}\,k_{\bot}^{2}\,e^{e^{-\imath\,(p_{i}\,-\,k_{i})(x_{i}\,-\,y_{i})}}\,\int\,\frac{dp_{+}dp_{-}}{\left(2p_{+}\,p_{-}\,-\,p_{\bot}^{2}\,+\,\imath\varepsilon\right)\,\left(2p_{+}\,p_{-}\,-\,k_{\bot}^{2}\,+\,\imath\varepsilon\right)}\,.\frac{1}{\left(p_{+}\,-\,\imath\varepsilon\right)^{2}\,\left(p_{-}\,-\,\imath\varepsilon\right)^{2}}\,$

and it provides almost the same contribution as Eq. (C.23) answer does:

$2\,\imath\,S_{xy\,1\,1\,3}\,=\,\frac{\imath}{4\pi}\,\partial_{i\,x}^{2}\,\partial_{i\,y}^{2}\,\int\frac{dp_{-}}{p_{-}}\,\int\frac{d^{2}p_{\bot}}{(2\pi)^{2}}\,\int\frac{d^{2}k_{\bot}}{(2\pi)^{2}}\,e^{-\imath\,(p_{i}\,-\,k_{i})(x_{i}\,-\,y_{i})}\,\frac{p_{\bot}^{2}\,+\,k_{\bot}^{2}}{p_{\bot}^{2}\,k_{\bot}^{2}}\,,$
(C.24)

this terms is absent in the $\gamma\,=\,0$ case of course.

##  Appendix D  Effective vertices of interaction of reggeized gravitons

The interaction term we obtain after the integration in respect to
$\epsilon_{\pm i}$ fluctuation has the following form:

$\displaystyle S_{int}\,$ $\displaystyle=$
$\displaystyle-\frac{1}{4\kappa^{2}}\int\,d^{4}x\,d^{4}y\,\left(\partial_{i}^{2}\mathcal{B}_{++}\partial_{j}\partial_{-}^{-1}B_{--}+\partial_{i}^{2}\mathcal{B}_{--}\mathcal{B}_{++}\partial_{j}\partial_{-}^{-1}\right)\,G_{0\,-j+k}(x,y)\left(\partial_{k}\partial_{+}^{-1}\partial_{i}^{2}\mathcal{B}_{++}\mathcal{B}_{--}+\partial_{i}^{2}\mathcal{B}_{--}\partial_{k}\partial_{+}^{-1}B_{++}\right)\,+\,$
(D.1) $\displaystyle+$
$\displaystyle\frac{1}{4\kappa}\,\int\,d^{4}x\,\partial_{i}^{2}\mathcal{B}_{++}\,\partial_{j}\partial_{-}^{-1}B_{--}\,\partial_{j}\partial_{-}^{-1}\epsilon_{--}\,+\,\frac{1}{4\kappa}\,\int\,d^{4}x\,\partial_{i}^{2}\mathcal{B}_{--}\,\partial_{j}\partial_{+}^{-1}B_{++}\,\partial_{j}\partial_{-}^{-1}\epsilon_{++}\,-\,$
$\displaystyle+$
$\displaystyle\frac{1}{4\kappa}\,\int\,d^{4}x\,\partial_{i}^{2}\mathcal{B}_{--}\,\mathcal{B}_{++}\,\partial_{j}^{2}\partial_{-}^{-1}\partial_{-}^{-1}\epsilon_{--}\,+\,\frac{1}{4\kappa}\,\int\,d^{4}x\,\partial_{i}^{2}\mathcal{B}_{++}\,\mathcal{B}_{--}\,\partial_{j}^{2}\partial_{+}^{-1}\partial_{-}^{-1}\epsilon_{++}\,+\,$
$\displaystyle+$
$\displaystyle\frac{1}{4\kappa}\,\int\,d^{4}x\,\partial_{i}^{2}\mathcal{B}_{++}\,\partial_{j}^{2}\partial_{+}^{-1}\partial_{+}^{-1}\mathcal{B}_{++}\,\epsilon_{--}\,+\,\frac{1}{4\kappa}\,\int\,d^{4}x\,\partial_{i}^{2}\mathcal{B}_{--}\,\partial_{j}^{2}\partial_{-}^{-1}\partial_{-}^{-1}\mathcal{B}_{--}\,\epsilon_{++}\,+\,$
$\displaystyle+$
$\displaystyle\,\frac{1}{8\kappa}\,\int\,d^{4}x\,\partial_{i}^{2}\mathcal{B}_{++}\,\left(\partial_{i}\partial_{-}^{-1}\mathcal{B}_{--}\right)^{2}\,+\,\frac{1}{8\kappa}\,\int\,d^{4}x\,\partial_{i}^{2}\mathcal{B}_{--}\,\left(\partial_{i}\partial_{+}^{-1}\mathcal{B}_{++}\right)^{2}\,+\,$
$\displaystyle+$
$\displaystyle\frac{1}{4\kappa}\,\int\,d^{4}x\,\partial_{i}^{2}\mathcal{B}_{--}\,\mathcal{B}_{++}\,\partial_{j}^{2}\partial_{-}^{-1}\partial_{-}^{-1}\mathcal{B}_{--}\,+\,\frac{1}{4\kappa}\,\int\,d^{4}x\,\partial_{i}^{2}\mathcal{B}_{++}\,\mathcal{B}_{--}\,\partial_{j}^{2}\partial_{-}^{-1}\partial_{-}^{-1}\mathcal{B}_{++}\,.$

Now, after the integrating out the $\varepsilon_{\pm}$ fluctuations, we have
correspondingly:

$\displaystyle S_{int}(\mathcal{B})\,$ $\displaystyle=$
$\displaystyle-\frac{1}{4\kappa^{2}}\int\,d^{4}x\,d^{4}y\,\left(\partial_{i}^{2}\mathcal{B}_{++}\partial_{j}\partial_{-}^{-1}B_{--}+\partial_{i}^{2}\mathcal{B}_{--}\mathcal{B}_{++}\partial_{j}\partial_{-}^{-1}\right)\,G_{0\,-j+k}(x,y)\left(\partial_{k}\partial_{+}^{-1}\partial_{i}^{2}\mathcal{B}_{++}\mathcal{B}_{--}+\partial_{i}^{2}\mathcal{B}_{--}\partial_{k}\partial_{+}^{-1}B_{++}\right)\,-\,$
(D.2) $\displaystyle-$
$\displaystyle\,\frac{1}{16\kappa^{2}}\,\int\,d^{4}x\,d^{4}y\,\left(\partial_{i}^{2}\mathcal{B}_{++}\,\partial_{j}\partial_{-}^{-1}\mathcal{B}_{--}\,\partial_{j}\partial_{-}^{-1}+\partial_{i}^{2}\mathcal{B}_{++}\,\partial_{j}^{2}\partial_{+}^{-1}\partial_{+}^{-1}\mathcal{B}_{++}\right)G_{\,--\,++}(x,y)\,\left(\partial_{k}\partial_{+}^{-1}\partial_{i}^{2}\mathcal{B}_{--}\,\partial_{k}\partial_{+}^{-1}\mathcal{B}_{++}\,+\,\right.$
$\displaystyle+$
$\displaystyle\left.\partial_{i}^{2}\mathcal{B}_{--}\,\partial_{j}^{2}\partial_{-}^{-1}\partial_{-}^{-1}\mathcal{B}_{--}\right)\,-\,$
$\displaystyle-$
$\displaystyle\frac{1}{32\kappa^{2}}\,\int\,d^{4}x\,d^{4}y\,\left(\left(\partial_{i}^{2}\mathcal{B}_{++}\right)\,\left(\partial_{j}\partial_{-}^{-1}\mathcal{B}_{--}\right)\right)\,\left(\partial_{j}\partial_{-}^{-1}\,G_{\,--\,--}(x,y)\,\partial_{k}\partial_{-}^{-1}\,\right)\,\left(\left(\partial_{i}^{2}\mathcal{B}_{++}\right)\,\left(\partial_{k}\partial_{-}^{-1}\mathcal{B}_{--}\right)\right)\,-\,$
$\displaystyle-$
$\displaystyle\frac{1}{32\kappa^{2}}\,\int\,d^{4}x\,d^{4}y\,\left(\left(\partial_{i}^{2}\mathcal{B}_{--}\right)\,\left(\partial_{j}\partial_{+}^{-1}\mathcal{B}_{++}\right)\right)\,\left(\partial_{j}\partial_{+}^{-1}\,G_{\,++\,++}(x,y)\,\partial_{k}\partial_{+}^{-1}\,\right)\,\left(\left(\partial_{i}^{2}\mathcal{B}_{--}\right)\,\left(\partial_{k}\partial_{+}^{-1}\mathcal{B}_{++}\right)\right)\,+\,$
$\displaystyle+$
$\displaystyle\frac{1}{8\kappa}\,\int\,d^{4}x\,\partial_{i}^{2}\mathcal{B}_{++}\,\left(\partial_{i}\partial_{-}^{-1}\mathcal{B}_{--}\right)^{2}\,+\,\frac{1}{8\kappa}\,\int\,d^{4}x\,\partial_{i}^{2}\mathcal{B}_{--}\,\left(\partial_{i}\partial_{+}^{-1}\mathcal{B}_{++}\right)^{2}\,.$

The terms represents LO interaction terms between reggeized gravitons and can
be used for the calculations of unitary corrections to the amplitudes.

## References

  * [1] T. Regge, Nuovo Cim. 18 (1960), 947-956.
  * [2] L. N. Lipatov, Sov. J. Nucl. Phys. 23, 338 (1976) [Yad. Fiz. 23 (1976) 642]; E. A. Kuraev, L. N. Lipatov and V. S. Fadin, Sov. Phys. JETP 45, 199 (1977) [Zh. Eksp. Teor. Fiz. 72, 377 (1977)]; I. I. Balitsky and L. N. Lipatov, Sov. J. Nucl. Phys. 28, 822 (1978) [Yad. Fiz. 28, 1597 (1978)].
  * [3] V. N. Gribov, Sov. Phys. JETP 26 (1968) 414.
  * [4] L. N. Lipatov, Nucl. Phys. B 452, 369 (1995); Phys. Rept. 286, 131 (1997); L. N. Lipatov, Phys. Rept. 286 (1997), 131-198;
  * [5] S. Bondarenko, L. Lipatov and A. Prygarin, Eur. Phys. J. C 77 (2017) no.8, 527; S. Bondarenko, L. Lipatov, S. Pozdnyakov and A. Prygarin, Eur. Phys. J. C 77 (2017) no. 9, 630.
  * [6] L. N. Lipatov, Phys. Lett. B 116 (1982), 411-413; Sov. Phys. JETP 55 (1982), 582-590; Nucl. Phys. B 365 (1991), 614-632; Subnucl. Ser. 49, 131 (2013); Int. J. Mod. Phys. Conf. Ser. 39, 1560082 (2015); Int. J. Mod. Phys. A 31, no. 28/29, 1645011 (2016); EPJ Web Conf. 125, 01010 (2016).
  * [7] L. N. Lipatov, Phys. Part. Nucl. 44 (2013), 391-413.
  * [8] J. Bartels, L. N. Lipatov and A. Sabio Vera, JHEP 07 (2014), 056.
  * [9] V. S. Fadin, R. Fiore and A. Papa, Nucl. Phys. B 769, (2007) 108; V. S. Fadin and R. Fiore, Phys. Lett. B 294 (1992) 286; V. S. Fadin, R. Fiore and A. Quartarolo, Phys. Rev. D 50 (1994) 2265; V. S. Fadin, R. Fiore and A. Papa, Phys. Rev. D 63 (2001) 034001; V. S. Fadin and R. Fiore, Phys. Rev. D 64 (2001) 114012; V. S. Fadin, M. G. Kozlov and A. V. Reznichenko, Phys. Atom. Nucl. 67 (2004) 359 [Yad. Fiz. 67 (2004) 377]; M. G. Kozlov, A. V. Reznichenko and V. S. Fadin, Phys. Atom. Nucl. 75 (2012) 850
  * [10] S. Bondarenko and S. S. Pozdnyakov, Phys. Lett. B 783 (2018) 207; S. Bondarenko and S. Pozdnyakov, Int. J. Mod. Phys. A 33 (2018) no.35, 1850204; S. Bondarenko and S. Pozdnyakov, Nucl. Phys. B 951 (2020), 114854.
  * [11] L.D. Faddeev, A.A. Slavnov, ”Gauge Fields. Introduction to Quantum Theory”, The Benjamin Cummings Publishing Company, 1980; I.Y.Arefeva, L.D.Faddeev and A.A.Slavnov, Theor. Math. Phys. 21, 1165 (1975) [Teor. Mat. Fiz. 21, 311 (1974)].
  * [12] S. Bondarenko and S. Pozdnyakov, Phys. Lett. B 783 (2018), 207-211.
  * [13] H. Raj and R. Venugopalan, Phys. Rev. D 109 (2024) no.4, 044064; H. Raj and R. Venugopalan, [arXiv:2312.11652 [hep-ph]]; H. Raj and R. Venugopalan, arXiv:2406.10483 [hep-th].
  * [14] A. Sabio Vera, E. Serna Campillo and M. A. Vazquez-Mozo, JHEP 03 (2012), 005; A. Sabio Vera, E. Serna Campillo and M. A. Vazquez-Mozo, JHEP 04 (2013), 086; A. Sabio Vera and M. A. Vazquez-Mozo, JHEP 03 (2015), 070; H. Johansson, A. Sabio Vera, E. Serna Campillo and M. Á. Vázquez-Mozo, JHEP 10 (2013), 215.
  * [15] S. Bondarenko, S. Pozdnyakov and M. A. Zubkov, Eur. Phys. J. C 81 (2021) no.7, 613.
  * [16] P. V. Landshoff and O. Nachtmann, Z. Phys. C 35 (1987), 405; O. Nachtmann, Annals Phys. 209 (1991), 436-478; E. Meggiolaro, Phys. Rev. D 53 (1996), 3835-3845; O. Nachtmann, Lect. Notes Phys. 479 (1997) 49; E. Meggiolaro, Nucl. Phys. B 602 (2001) 261; E. Laenen, G. Stavenga and C. D. White, JHEP 03 (2009), 054.
  * [17] S. Bondarenko and M. A. Zubkov, Eur. Phys. J. C 78 (2018) no.8, 617.
  * [18] C. D. White, JHEP 05 (2011), 060; V. Del Duca, C. Duhr, E. Gardi, L. Magnea and C. D. White, JHEP 12 (2011), 021; S. G. Naculich and H. J. Schnitzer, JHEP 05 (2011), 087; M. Beneke and G. Kirilin, JHEP 09 (2012), 066; S. Melville, S. G. Naculich, H. J. Schnitzer and C. D. White, Phys. Rev. D 89 (2014) no.2, 025009; D. Bonocore, A. Kulesza and J. Pirsch, JHEP 03 (2022), 147.
  * [19] D. Amati, M. Ciafaloni and G. Veneziano, Nucl. Phys. B 403 (1993), 707-724; . Fabbrichesi, R. Pettorino, G. Veneziano and G. A. Vilkovisky, Nucl. Phys. B 419 (1994), 147-188; D. Amati, M. Ciafaloni and G. Veneziano, JHEP 02 (2008), 049; M. Ciafaloni, D. Colferai and G. Veneziano, Phys. Rev. D 99 (2019) no.6, 066008; A. Addazi, M. Bianchi and G. Veneziano, JHEP 05 (2019), 050; P. Di Vecchia, C. Heissenberg, R. Russo and G. Veneziano, JHEP 07 (2021), 169; P. Di Vecchia, C. Heissenberg, R. Russo and G. Veneziano, arXiv:2306.16488 [hep-th].
  * [20] J. F. Donoghue, Phys. Rev. D 50 (1994), 3874-3888; J. F. Donoghue and D. Wyler, Phys. Rev. D 81 (2010), 114023; J. Donoghue, Scholarpedia 12 (2017) no.4, 32997; J. F. Donoghue, arXiv:2211.09902 [hep-th].
  * [21] Scherk, John, and John H. Schwarz, General Relativity and Gravitation 6 (1975), 537-550.
  * [22] L. D. Landau and E. M. Lifschits,”The Classical Theory of Fields”’, Vol2, Pergamon Press, 1975.
  * [23] I. Balitsky, Nucl. Phys. B463 (1996) 99; Phys. Rev. D 60, 014020 (1999); In *Shifman, M. (ed.): At the frontier of particle physics, vol. 2* 1237-1342; Nucl. Phys. B 629, 290 (2002).
  * [24] Maggiore, Michele, ”Gravitational waves: Volume 1: Theory and experiments”’, OUP Oxford, 2007.
  * [25] J. F. Donoghue, M. M. Ivanov and A. Shkerin, arXiv:1702.00319 [hep-th].
  * [26] Y. V. Kovchegov, Phys. Rev. D60 (1999) 034008; Phys. Rev. D61 (2000) 074018.
  * [27] S. Bondarenko, S. Pozdnyakov and A. Prygarin, Eur. Phys. J. C 81 (2021) no.9, 793.
  * [28] F. Caporale, G. Chachamis, B. Murdaca and A. Sabio Vera, Phys. Rev. Lett. 116 (2016) no.1, 012001; F. G. Celiberto, D. Gordo Gómez and A. Sabio Vera, Phys. Lett. B 786 (2018), 201-206; R. D. Ball, V. Bertone, M. Bonvini, S. Marzani, J. Rojo and L. Rottoli, Eur. Phys. J. C 78 (2018) no.4, 321; A. Sabio Vera, arXiv:2001.11941 [hep-ph]; D. Colferai, F. Deganutti, T. G. Raben and C. Royon, JHEP 06 (2023), 091; C. Royon, Acta Phys. Polon. Supp. 16 (2023) no.5, 36; M. Hentschinski, C. Royon, M. A. Peredo, C. Baldenegro, A. Bellora, R. Boussarie, F. G. Celiberto, S. Cerci, G. Chachamis and J. G. Contreras, et al. Acta Phys. Polon. B 54 (2023) no.3, 3-A2.
  * [29] S. Bondarenko, E. Gotsman, E. Levin and U. Maor, Nucl. Phys. A 683 (2001), 649-691.