6533b834fe1ef96bd129e1e7
RESEARCH PRODUCT
On fixed points of the Burrows-Wheeler transform
Floriana RussoAntonio RestivoSabrina MantaciGiovanna RosoneMarinella Sciortinosubject
Discrete mathematicsAlgebra and Number TheoryBurrows–Wheeler transformSettore INF/01 - InformaticaPermutationPermutations0102 computer and information sciences02 engineering and technologyInformation SystemFixed point01 natural sciencesTheoretical Computer ScienceComputational Theory and Mathematics010201 computation theory & mathematicsFixed PointFixed Points0202 electrical engineering electronic engineering information engineeringBurrows-Wheeler Transform; Fixed Points; Permutations; Theoretical Computer Science; Algebra and Number Theory; Information Systems; Computational Theory and Mathematics020201 artificial intelligence & image processingBurrows-Wheeler TransformInformation SystemsMathematicsdescription
The Burrows-Wheeler Transform is a well known transformation widely used in Data Compression: important competitive compression software, such as Bzip (cf. [1]) and Szip (cf. [2]) and some indexing software, like the FM-index (cf. [3]), are deeply based on the Burrows Wheeler Transform. The main advantage of using BWT for data compression consists in its feature of "clustering" together equal characters. In this paper we show the existence of fixed points of BWT, i.e., words on which BWT has no effect. We show a characterization of the permutations associated to BWT of fixed points and we give the explicit form of fixed points on a binary ordered alphabet a, b having at most four b's and those having at most four a's.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2017-08-09 |