Name
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 any purely morphic finite word on a binary alphabet, $r_{bwt}$ is $\mathcal{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 \emph{bispecial circular factors} of such words. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1007/978-3-031-05578-2_11 | International Conference on Developments in Language Theory (DLT) |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrea Frosini | 1 | 101 | 20.44 |
| Ilaria Mancini | 2 | 0 | 0.34 |
| Simone Rinaldi | 3 | 0 | 1.35 |
| Giuseppe Romana | 4 | 0 | 1.01 |
| Marinella Sciortino | 5 | 1 | 1.74 |