Unclustered BWTs of any Length over Non-Binary Alphabets
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911127868276736 |
|---|---|
| author | Fici, Gabriele Gabory, Estéban Romana, Giuseppe Sciortino, Marinella |
| author_facet | Fici, Gabriele Gabory, Estéban Romana, Giuseppe Sciortino, Marinella |
| contents | We prove that for every integer $n > 0$ and for every alphabet $Σ_k$ of size $k \geq 3$, there exists a necklace of length $n$ whose Burrows-Wheeler Transform (BWT) is completely unclustered, i.e., it consists of exactly $n$ runs with no two consecutive equal symbols. These words represent the worst-case behavior of the BWT for clustering, since the number of BWT runs is maximized. We also establish a lower bound on their number. This contrasts with the binary case, where the existence of infinitely many completely unclustered BWTs is still an open problem, related to Artin's conjecture on primitive roots. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_20879 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Unclustered BWTs of any Length over Non-Binary Alphabets Fici, Gabriele Gabory, Estéban Romana, Giuseppe Sciortino, Marinella Discrete Mathematics Data Structures and Algorithms Formal Languages and Automata Theory Combinatorics We prove that for every integer $n > 0$ and for every alphabet $Σ_k$ of size $k \geq 3$, there exists a necklace of length $n$ whose Burrows-Wheeler Transform (BWT) is completely unclustered, i.e., it consists of exactly $n$ runs with no two consecutive equal symbols. These words represent the worst-case behavior of the BWT for clustering, since the number of BWT runs is maximized. We also establish a lower bound on their number. This contrasts with the binary case, where the existence of infinitely many completely unclustered BWTs is still an open problem, related to Artin's conjecture on primitive roots. |
| title | Unclustered BWTs of any Length over Non-Binary Alphabets |
| topic | Discrete Mathematics Data Structures and Algorithms Formal Languages and Automata Theory Combinatorics |
| url | https://arxiv.org/abs/2508.20879 |