On Fixed Points of the Burrows-Wheeler Transform

Issue title: Elegant Structures in Computation. To Andrzej Ehrenfeucht on His 85th Birthday

Guest editors: Gheorghe Păun, Grzegorz Rozenberg and Arto Salomaa

Article type: Research Article

Authors: Mantaci, Sabrina^{a; *} | Restivo, Antonio^b | Rosone, Giovanna^{c; *; †} | Russo, Floriana^d | Sciortino, Marinella^{e; *}

Affiliations: [a] Dipartimento di Matematica e Informatica, University of Palermo, Italy. sabrina.mantaci@unipa.it | [b] Dipartimento di Matematica e Informatica, University of Palermo, Italy. antonio.restivo@unipa.it | [c] Dipartimento di Informatica, University of Pisa, Italy. giovanna.rosone@unipi.it | [d] Dipartimento di Matematica e Informatica, University of Palermo, Italy. floriana.russo01@community.unipa.it | [e] Dipartimento di Matematica e Informatica, University of Palermo, Italy. marinella.sciortino@unipa.it

Correspondence: [†] Address for correspondence: Dipartimento di Informatica, University of Pisa, Italy

Note: [*] Partially supported by the project MIUR-SIR CMACBioSeq (“Combinatorial methods for analysis and compression of biological sequences”) grant n. RBSI146R5 and by the Gruppo Nazionale per il Calcolo Scientifico (GNCS-INDAM)

Abstract: 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.

Keywords: Burrows-Wheeler Transform, Permutations, Fixed Points

DOI: 10.3233/FI-2017-1566

Journal: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 277-288, 2017