Morphisms and BWT-run Sensitivity
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_ | 1866910917979013120 |
|---|---|
| author | Fici, Gabriele Romana, Giuseppe Sciortino, Marinella Urbina, Cristian |
| author_facet | Fici, Gabriele Romana, Giuseppe Sciortino, Marinella Urbina, Cristian |
| contents | We study how the application of injective morphisms affects the number $r$ of equal-letter runs in the Burrows-Wheeler Transform (BWT). This parameter has emerged as a key repetitiveness measure in compressed indexing. We focus on the notion of BWT-run sensitivity after application of an injective morphism. For binary alphabets, we characterize the class of morphisms that preserve the number of BWT-runs up to a bounded additive increase, by showing that it coincides with the known class of primitivity-preserving morphisms, which are those that map primitive words to primitive words. We further prove that deciding whether a given binary morphism has bounded BWT-run sensitivity is possible in polynomial time with respect to the total length of the images of the two letters. Additionally, we explore new structural and combinatorial properties of synchronizing and recognizable morphisms. These results establish new connections between BWT-based compressibility, code theory, and symbolic dynamics. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_17443 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Morphisms and BWT-run Sensitivity Fici, Gabriele Romana, Giuseppe Sciortino, Marinella Urbina, Cristian Formal Languages and Automata Theory Discrete Mathematics Data Structures and Algorithms Combinatorics We study how the application of injective morphisms affects the number $r$ of equal-letter runs in the Burrows-Wheeler Transform (BWT). This parameter has emerged as a key repetitiveness measure in compressed indexing. We focus on the notion of BWT-run sensitivity after application of an injective morphism. For binary alphabets, we characterize the class of morphisms that preserve the number of BWT-runs up to a bounded additive increase, by showing that it coincides with the known class of primitivity-preserving morphisms, which are those that map primitive words to primitive words. We further prove that deciding whether a given binary morphism has bounded BWT-run sensitivity is possible in polynomial time with respect to the total length of the images of the two letters. Additionally, we explore new structural and combinatorial properties of synchronizing and recognizable morphisms. These results establish new connections between BWT-based compressibility, code theory, and symbolic dynamics. |
| title | Morphisms and BWT-run Sensitivity |
| topic | Formal Languages and Automata Theory Discrete Mathematics Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2504.17443 |