Salta al contenuto principale
Passa alla visualizzazione normale.


Burrows-Wheeler Transform on Purely Morphic Words

  • Autori: Frosini, A; Mancini, I; Rinaldi, S; Romana, G; Sciortino, M
  • Anno di pubblicazione: 2022
  • Tipologia: Contributo in atti di convegno pubblicato in volume
  • OA Link:


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 .