IJPAM: Volume 31, No. 1 (2006)

SIMPLE ALGORITHM FOR SORTING THE FIBONACCI
STRING ROTATIONS

Manolis Christodoulakis$^1$, Costas S. Iliopoulos$^2$,
Yoan José Pinzón Ardila$^3$
$^{1,2}$Department of Computer Science
King's College London
London, WC2R 2LS, U.K.
$^1$e-mail: manolis@dcs.kcl.ac.uk
$^2$e-mail: csi@dcs.kcl.ac.uk
$^3$Faculty of Informatics
Pontificia Bolivariana University
Km 7 Via Piedecuesta, COLOMBIA
e-mail: yoan@pinzon.co.uk


Abstract.In this paper we focus on the combinatorial properties of the Fibonacci strings rotations. We first present a simple formula that, in constant time, determines the rank of any rotation (of a given Fibonacci string) in the lexicographically-sorted list of all rotations. We then use this information to deduce, also in constant time, the character that is stored at any one location of any given Fibonacci string. Finally, we study the output of the Burrows-Wheeler Transform (BWT) on Fibonacci strings to prove that when BWT is applied to Fibonacci strings it always produces a sequence of `${\tt b}$'s followed by a sequence of `${\tt a}$'s.

Received: July 8, 2006

AMS Subject Classification: 26A33

Key Words and Phrases: block-sorting, Fibonacci strings, data compression, text compression, BWT transformation

Source: International Journal of Pure and Applied Mathematics
ISSN: 1311-8080
Year: 2006
Volume: 31
Issue: 1