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 ‘b’s’ followed by a sequence of ‘a’s’. |
Year | DOI | Venue |
---|---|---|
2006 | 10.1007/11611257_19 | SOFSEM |
Keywords | Field | DocType |
fibonacci string rotation,fibonacci string,lexicographically-sorted list,simple formula,constant time,combinatorial property,burrows-wheeler transform,fibonacci strings rotation,simple algorithm,burrows wheeler transform,data compression | Discrete mathematics,Fibonacci word,Combinatorics,Sorting,Lagged Fibonacci generator,Pisano period,Fibonacci search technique,String (computer science),Mathematics,Fibonacci polynomials,Fibonacci number | Conference |
Volume | ISSN | ISBN |
3831 | 0302-9743 | 3-540-31198-X |
Citations | PageRank | References |
0 | 0.34 | 3 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Manolis Christodoulakis | 1 | 64 | 9.49 |
Costas S. Iliopoulos | 2 | 1534 | 167.43 |
Yoan José Pinzón Ardila | 3 | 7 | 1.86 |