IJPAM: Volume 31, No. 1 (2006)
Yoan José Pinzón Ardila
Department of Computer Science
King's College London
London, WC2R 2LS, U.K.
Faculty of Informatics
Pontificia Bolivariana University
Km 7 Via Piedecuesta, COLOMBIA
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 `'s followed by a sequence of `'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