The study of the compressibility of repetitive sequences is an issue that is attracting great interest. We consider purely morphic words, which are highly repetitive sequences generated by iterating a morphism φ that admits a fixed point (denoted by φ^∞(a) ) starting from a given character a belonging to the finite alphabet A , i.e. φ^∞(a)=lim_{i→∞}φ^i(a) . Such morphisms are called prolongable on a . Here we focus on the compressibility via the Burrows-Wheeler Transform (BWT) of infinite families of finite sequences generated by morphisms. In particular, denoted by r(w) the number of equal-letter runs of a word w , we provide new upper bounds on r(bwt(φ^i(a))) , i.e. the number of equal-letter runs produced when BWT is applied on φ^i(a) . Such bounds depend on the factor complexity f_x(n) of the infinite word x=φ^∞(a) , that counts, for each n≥0 , the number of distinct factors of x having length n .

Frosini, A., Mancini, I., Rinaldi, S., Romana, G., Sciortino, M. (2022). Burrows-Wheeler Transform on Purely Morphic Words. In Data Compression Conference 2022 (pp. 452-452). 345 E 47TH ST, NEW YORK, NY 10017 USA : IEEE [10.1109/DCC52660.2022.00063].

Burrows-Wheeler Transform on Purely Morphic Words

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

Abstract

The study of the compressibility of repetitive sequences is an issue that is attracting great interest. We consider purely morphic words, which are highly repetitive sequences generated by iterating a morphism φ that admits a fixed point (denoted by φ^∞(a) ) starting from a given character a belonging to the finite alphabet A , i.e. φ^∞(a)=lim_{i→∞}φ^i(a) . Such morphisms are called prolongable on a . Here we focus on the compressibility via the Burrows-Wheeler Transform (BWT) of infinite families of finite sequences generated by morphisms. In particular, denoted by r(w) the number of equal-letter runs of a word w , we provide new upper bounds on r(bwt(φ^i(a))) , i.e. the number of equal-letter runs produced when BWT is applied on φ^i(a) . Such bounds depend on the factor complexity f_x(n) of the infinite word x=φ^∞(a) , that counts, for each n≥0 , the number of distinct factors of x having length n .
Settore INF/01 - Informatica
978-1-6654-7893-9
https://ieeexplore.ieee.org/document/9810723
Frosini, A., Mancini, I., Rinaldi, S., Romana, G., Sciortino, M. (2022). Burrows-Wheeler Transform on Purely Morphic Words. In Data Compression Conference 2022 (pp. 452-452). 345 E 47TH ST, NEW YORK, NY 10017 USA : IEEE [10.1109/DCC52660.2022.00063].
File in questo prodotto:
File Dimensione Formato  
Burrows-Wheeler_Transform_on_Purely_Morphic_Words.pdf

Solo gestori archvio

Tipologia: Versione Editoriale
Dimensione 82 kB
Formato Adobe PDF
82 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/575150
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact