Measuring sequence similarity and compressing texts are among the most fundamental
tasks in string algorithms. In this work, we develop near-optimal quantum algorithms for the …

We show that the size γ (t_n) of the smallest string attractor of the n-th Thue-Morse word t_n
is 4 for any n ≥ 4, disproving the conjecture by Mantaci et al. ICTCS 2019 that it is n. We …

We propose algorithms that, given the input string of length n over integer alphabet of size σ,
construct the Burrows–Wheeler transform (BWT), the permuted longest-common-prefix …

Motivated by applications to string processing, we introduce variants of the Lyndon
factorization called inverse Lyndon factorizations. Their factors, named inverse Lyndon …

The so-called “one-bit catastrophe” for the compression algorithm LZ'78 asks whether the
compression ratio of an infinite word can change when a single bit is added in front of it. We …

This work establishes several strong hardness results on the problem of finding an ordering
on a string's alphabet that either minimizes or maximizes the number of factors in that string's …

Lempel-Ziv (LZ) factorization and Lyndon factorization are well-known factorizations of
strings. Recently, Kärkkäinen et al. studied the relation between the sizes of the two …

Graph pangenomics is a new emerging field in computational biology that is changing the
traditional view of a reference genome from a linear sequence to a new paradigm: a …

The Lyndon factorization of a word has been largely studied and recently variants of it have
been introduced and investigated with different motivations. In particular, the canonical …

The Lyndon factorization of a word has been extensively studied in different contexts and
several variants of it have been proposed. In particular, the canonical inverse Lyndon …