Logarithmic equal-letter runs for BWT of purely morphic words

التفاصيل البيبلوغرافية
العنوان: Logarithmic equal-letter runs for BWT of purely morphic words
المؤلفون: Frosini, Andrea, Mancini, Ilaria, Rinaldi, Simone, Romana, Giuseppe, Sciortino, Marinella
سنة النشر: 2022
المجموعة: Computer Science
مصطلحات موضوعية: Computer Science - Formal Languages and Automata Theory, Computer Science - Data Structures and Algorithms
الوصف: 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.
نوع الوثيقة: Working Paper
URL الوصول: http://arxiv.org/abs/2202.02609
رقم الأكسشن: edsarx.2202.02609
قاعدة البيانات: arXiv