6533b7d3fe1ef96bd12600b5

RESEARCH PRODUCT

Logarithmic Equal-Letter Runs for BWT of Purely Morphic Words

Andrea FrosiniIlaria ManciniSimone RinaldiGiuseppe RomanaMarinella Sciortino

subject

Equal-letter runsSettore INF/01 - InformaticaMorphismsBurrows-Wheeler TransformBispecial circular factors

description

In this paper we study the number r(bwt) of equal-letter runs produced by the Burrows-Wheeler transform (BWT) when it is applied to purely morphic finite words, which are words generated by iterating prolongable morphisms. Such a parameter r(bwt) is very significant since it provides a measure of the performances of the BWT, in terms of both compressibility and indexing. In particular, we prove that, when BWT is applied to whichever purely morphic finite word on a binary alphabet, r(bwt) is O(log n), where n is the length of the word. Moreover, we prove that r(bwt) is Theta(log n) for the binary words generated by a large class of prolongable binary morphisms. These bounds are proved by providing some new structural properties of the bispecial circular factors of such words.

yearjournalcountryeditionlanguage
2022-01-01
https://doi.org/10.1007/978-3-031-05578-2_11