2026-09-27T04:28:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25939 2026-09-23T23:56:14Z ddc:004 open_access

Totally Unclustered BWT Images of Any Length over Non-Binary Alphabets Fici, Gabriele Gabory, Estéban Romana, Giuseppe Sciortino, Marinella Burrows-Wheeler Transform BWT-runs Repetitiveness Measure Clustering Effect Generalized de Bruijn Words 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gabriele Fici and Estéban Gabory and Giuseppe Romana and Marinella Sciortino 2026 Is Part Of LIPIcs, Volume 369, 37th Annual Symposium on Combinatorial Pattern Matching (CPM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2026.13 urn:nbn:de:0030-drops-259399 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2026.13 eng https://creativecommons.org/licenses/by/4.0/legalcode