Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6875901 | Theoretical Computer Science | 2017 | 9 Pages |
Abstract
More in general we show that the application of BWT to any word at worst doubles the number of equal-letter runs. Moreover, we prove that this bound is tight by exhibiting some families of words where such upper bound is always reached. We also prove that for binary words the case in which the BWT produces the maximal number of clusters is related to the very well known Artin's conjecture on primitive roots. The study of some combinatorial properties underlying this transformation could be useful for improving indexing and compression strategies.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Sabrina Mantaci, Antonio Restivo, Giovanna Rosone, Marinella Sciortino, Luca Versari,