Morphisms and BWT-run Sensitivity

Gabriele Fici, Giuseppe Romana, Marinella Sciortino, Cristian Urbina · 2025

Read Morphisms and BWT-run Sensitivity by Gabriele Fici, Giuseppe Romana, Marinella Sciortino, Cristian Urbina (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-17443.txt.

Introduction

Gabriele Fici, Giuseppe Romana, Marinella Sciortino, and Cristian Urbina study how word-rewriting rules change a key measure of text repetitiveness, in a 2025 paper. The measure counts runs of equal letters in a famous reordering of a text, the Burrows-Wheeler transform, which underpins modern compressed search. A rewriting rule, a morphism, swaps each letter for a fixed block. The team asks which rules keep the run count nearly steady.

For two-letter alphabets, they pin the safe rules down exactly: they are the rules long known to preserve primitivity, the property of words that are not repeats of a shorter word. They also show that testing a rule for safety runs in fast, polynomial time. Side results probe two related rule classes. The work ties compression to older fields of codes and symbol dynamics.

Catalog record

CREATORGabriele Fici, Giuseppe Romana, Marinella Sciortino, Cristian Urbina
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE71 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-17443

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Morphisms and BWT-run Sensitivity Gabriele Fici, Giuseppe Romana, Marinella Sciortino, Cristian Urbina Abstract We study how the application of injective morphisms affects the number r 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. Department of Mathematics and Computer Science, University of Palermo, [email protected]://orcid.org/0000-0002-3536-327XSupported by MUR project PRIN 2022 APML – 20229BCXNW, funded by the European Union – Mission 4 ”Education and Research” C2 - Investment 1.1.Department of Mathematics and Computer Science, University of Palermo, [email protected]://orcid.org/0000-0002-3489-0684Supported by the MUR PRIN Project “PINC, Pangenome INformatiCs: from Theory to Applications” (Grant No. 2022YRB97K), funded by Next Generation EU PNRR M4 C2, Inv. 1.1. Department of Mathematics and Computer Science, University of Palermo, [email protected]://orcid.org/0000-0001-6928-0168Supported by the project “ACoMPA – Algorithmic and Combinatorial Methods for Pangenome Analysis” (CUP B73C24001050001) funded by the NextGeneration EU programme PNRR ECS00000017 Tuscany Health Ecosystem (Spoke 6), Mission 4, Component 2. Department of Computer Science, University of Chile, Santiago, Chile and Centre for Biotechnology and Bioengineering (CeBiB), Santiago, [email protected]://orcid.org/0000-0001-8979-9055Basal Funds FB0001 and AFB240001; Fondecyt Grant 1-230755, ANID, Chile; ANID-Subdirección de Capital Humano/Doctorado Nacional/2021-21210580, ANID, Chile. ccs Theory of computation → Design and analysis of algorithms, Theory of computation → Formal languages and automata theory, Mathematics of computing → Combinatorics on words keywords Burrows–Wheeler transform, BWT-runs, morphism, pure code, repetitiveness † † runningtitle: Morphisms and BWT-run Sensitivity † † runningauthor: G. Fici, G. Romana, M. Sciortino, C. Urbina † † copyright: Gabriele Fici, Giuseppe Romana, Marinella Sciortino and Cristian Urbina † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction Morphisms are a powerful combinatorial mechanism for generating a collection of repetitive texts, and have been largely used in the field of combinatorics on words and formal languages [ 18 , 28 ] . Formally, a morphism maps each character of an alphabet to a word over the same or another alphabet, by preserving the operation of concatenation. That is, if \mu is a morphism and u and v are words, then \mu(uv)=\mu(u)\mu(v) . Iterating morphisms can produce long and often highly repetitive sequences, which makes them a natural model for studying repetitiveness in words. Morphisms find applications in a wide range of contexts. Injective morphisms are widely used in information theory, data compression, and cryptography, as they define uniquely decodable codes [ 3 ] . More recently, morphisms have been employed in combination with copy-paste mechanisms to define novel compression schemes, known as NU-systems [ 24 ] , further highlighting their versatility in modeling and processing repetitive data. The Burrows–Wheeler Transform (BWT) is a reversible transformation introduced in 1994 in the field of data compression [ 5 ] and now underpins some of the most used tools in bioinformatics, such as bwa [ 17 , 32 ] and bowtie [ 16 , 15 ] . It permutes the characters of a text in a way that makes it more compressible, by clustering characters that precede similar contexts in the text. This property often results in long runs of identical characters, particularly in repetitive texts. The number r of such equal-letter runs, known as BWT-runs , has recently emerged as a measure of repetitiveness [ 23 ] . Several measures have been proposed to quantify repetitiveness in strings [ 22 ] , such as the number z of phrases in the Lempel–Ziv parsing, the size g of the smallest context-free grammar generating the text, the size \gamma of the smallest string attractor [ 14 , 6 ] . Among these, the measure r has recently attracted considerable attention due to its close connection with compressed indexing structures, such as the r -index [ 10 ] , which use space proportional to r and support efficient pattern matching and retrieval in highly repetitive text collections, including genomic datasets and versioned document archives. Akagi et al. [ 1 ] explored the question of how much one character edit affects compression-based repetitiveness measures. In [ 11 ] , the effect of single edit operations on the measure r has also been analyzed. In this paper, we study how the application of an injective morphism affects the measure r , i.e., the number of BWT-runs. We focus on two notions of BWT-run sensitivity , which capture how much the number of BWT-runs can change when a morphism \mu is applied to a word. The additive sensitivity function AS_{\mu} gives, for every n>0 , the maximum increase in the number of BWT-runs that can occur when applying the morphism \mu to any word of length n , while the multiplicative sensitivity function MS_{\mu} gives, for every n>0 , the maximum ratio between the number of BWT-runs after and before the morphism \mu is applied, over all words of length n . These notions allow us to quantify the impact of a morphism on the compressibility of the resulting text. An initial approach to the study of how morphisms affect the number of BWT-runs was given in [ 9 ] , where we showed that Sturmian morphisms are the only binary injective morphisms that preserve the number of BWT-runs. Here, we tackle the problem of characterizing those binary injective morphisms that preserve the BWT-based compressibility of a text, in the sense that they have an additive sensitivity function bounded by a constant. We prove that this class coincides with the known class of primitivity-preserving morphisms , which are those that map primitive words to primitive words. As a direct consequence, for these morphisms the multiplicative sensitivity function is also bounded. Primitivity-preserving morphisms are a well-studied class in algebraic theory of codes, and they are crucial in applications involving symbolic sequences, code synchronization, and the structural analysis of words [ 30 , 27 , 8 , 21 , 18 , 3 , 12 ] . In addition to establishing a novel connection between BWT-based compressed indexing, combinatorics on words, and code theory, a key contribution of our paper consists in identifying new combinatorial and structural properties of primitivity-preserving, recognizable, and synchronizing morphisms. These properties are central to our main results but also hold independent interest in information theory and symbolic dynamics, where such morphisms play a fundamental role in coding, synchronization, and symbolic representations of dynamical systems [ 2 , 3 ] .

Read the complete text