We prove that for every integer n > 0 and for every alphabet Σk of size k ≥ 3, there exist words of length n whose Burrows–Wheeler Transform (BWT) is totally unclustered, i.e., it consists of exactly n runs with no two consecutive equal symbols. These words represent the worst-case behavior of the clustering effect of the BWT. We also establish a lower bound on their number. This contrasts with the binary case, where the existence of infinitely many totally unclustered BWT images is still an open problem, related to Artin’s conjecture on primitive roots.
Fici, G., Gabory, E., Romana, G., Sciortino, M. (2026). Totally Unclustered BWT Images of Any Length over Non-Binary Alphabets. In P. Bille, N. Prezza (a cura di), 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing [10.4230/LIPIcs.CPM.2026.13].
Totally Unclustered BWT Images of Any Length over Non-Binary Alphabets
Fici G.
;Romana G.;Sciortino M.
2026-01-01
Abstract
We prove that for every integer n > 0 and for every alphabet Σk of size k ≥ 3, there exist words of length n whose Burrows–Wheeler Transform (BWT) is totally unclustered, i.e., it consists of exactly n runs with no two consecutive equal symbols. These words represent the worst-case behavior of the clustering effect of the BWT. We also establish a lower bound on their number. This contrasts with the binary case, where the existence of infinitely many totally unclustered BWT images is still an open problem, related to Artin’s conjecture on primitive roots.
| File | Dimensione | Formato | |
|---|---|---|---|
|
LIPIcs.CPM.2026.13.pdf
accesso aperto
Tipologia:
Versione Editoriale
Dimensione
903.81 kB
Formato
Adobe PDF
|
903.81 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
