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.

Frosini, A., Mancini, I., Rinaldi, S., Romana, G., Sciortino, M. (2022). Logarithmic Equal-Letter Runs for BWT of Purely Morphic Words. In V. Diekert, M. Volkov (a cura di), Developments in Language Theory 26th International Conference, DLT 2022, Tampa, FL, USA, May 9–13, 2022, Proceedings (pp. 139-151). GEWERBESTRASSE 11, CHAM, CH-6330, SWITZERLAND : SPRINGER INTERNATIONAL PUBLISHING AG [10.1007/978-3-031-05578-2_11].

Logarithmic Equal-Letter Runs for BWT of Purely Morphic Words

Romana, G;Sciortino, M
2022-01-01

Abstract

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.
Settore INF/01 - Informatica
978-3-031-05577-5
978-3-031-05578-2
https://link.springer.com/chapter/10.1007/978-3-031-05578-2_11
Frosini, A., Mancini, I., Rinaldi, S., Romana, G., Sciortino, M. (2022). Logarithmic Equal-Letter Runs for BWT of Purely Morphic Words. In V. Diekert, M. Volkov (a cura di), Developments in Language Theory 26th International Conference, DLT 2022, Tampa, FL, USA, May 9–13, 2022, Proceedings (pp. 139-151). GEWERBESTRASSE 11, CHAM, CH-6330, SWITZERLAND : SPRINGER INTERNATIONAL PUBLISHING AG [10.1007/978-3-031-05578-2_11].
File in questo prodotto:
File Dimensione Formato  
Frosini2022_Chapter_LogarithmicEqual-LetterRunsFor.pdf

Solo gestori archvio

Tipologia: Versione Editoriale
Dimensione 296.49 kB
Formato Adobe PDF
296.49 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10447/575228
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact