7 papers
Unclustered BWTs of any Length over Non-Binary Alphabets
Gabriele Fici, Estéban Gabory, Giuseppe Romana +1
We prove that for every integer and for every alphabet of size , there exists a necklace of length whose Burrows-Wheeler Transform (BWT) is completely u…
String Consensus Problems with Swaps and Substitutions
Estéban Gabory, Laurent Bulteau, Gabriele Fici +1
String consensus problems aim at finding a string that minimizes some given distance with respect to an input set of strings. In particular, in the Closest string problem, we are g…
Morphisms and BWT-run Sensitivity
Gabriele Fici, Giuseppe Romana, Marinella Sciortino +1
We study how the application of injective morphisms affects the number of equal-letter runs in the Burrows-Wheeler Transform (BWT). This parameter has emerged as a key repetiti…
U-index: A Universal Indexing Framework for Matching Long Patterns
Lorraine A. K. Ayad, Gabriele Fici, Ragnar Groot Koerkamp +4
Text indexing is a fundamental and well-studied problem. Classic solutions either replace the original text with a compressed representation, e.g., the FM-index and its variants, o…
Generalized De Bruijn Words, Invertible Necklaces, and the Burrows-Wheeler Transform
Gabriele Fici, Estéban Gabory
We define generalized de Bruijn words as those words having a Burrows-Wheeler transform that is a concatenation of permutations of the alphabet. We show that generalized de Bruijn…
The Shortest Interesting Binary Words
Gabriele Fici
I will show that there exist two binary words (one of length 4 and one of length 6) that play a special role in many different problems in combinatorics on words. They can therefor…