[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Simple Algorithm for Sorting the Fibonacci String Rotations

  • Conference paper
SOFSEM 2006: Theory and Practice of Computer Science (SOFSEM 2006)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 3831))

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’.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Berstel, J.: Fibonacci Words—a Survey. In: Rozenberg, G., Salomaa, A. (eds.) The Book of L, pp. 13–27. Springer, Heidelberg (1986)

    Google Scholar 

  2. Knuth, D.E.: The Art of Computer Programming, 3rd edn., vol. 1. Addison-Wesley, Reading (1997)

    Google Scholar 

  3. Cummings, L.J., Smyth, W.F.: Weak Repetitions in Strings. The Journal of Combinatorial Mathematics and Combinatorial Computing 24, 33–48 (1997)

    MATH  MathSciNet  Google Scholar 

  4. Burrows, M., Wheeler, D.: A Block-Sorting Lossless Data Compression Algorithm. Technical Report 124, Digital Equipment Corporation (1994)

    Google Scholar 

  5. Mantaci, S., Restivo, A., Sciortino, M.: Burrows–Wheeler Transform and Sturmian Words. Information Processing Letters 86, 241–246 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  6. Iliopoulos, C.S., Moore, D., Smyth, W.F.: A Characterization of the Squares in a Fibonacci String. Theoretical Computer Science 172, 281–291 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  7. Eccles, P.: An Introduction to Mathematical Reasoning: Numbers, Sets and Functions. Cambridge University Press, Cambridge (1997)

    MATH  Google Scholar 

  8. Koshy, T.: Elementary Number Theory with Applications. Elsevier, Amsterdam (2001)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, King’s College London, London, WC2R 2LS, UK

    Manolis Christodoulakis, Costas S. Iliopoulos & Yoan José Pinzón Ardila

Authors
  1. Manolis Christodoulakis
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Costas S. Iliopoulos
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Yoan José Pinzón Ardila
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Institute of Computer Science, Academy of Sciences of the Czech Republic, Pod Vodárenskou věží 2, 182 07, Prague 8, Czech Republic

    Jiří Wiedermann  & Július Štuller  & 

  2. Department of Information and Computer Sciences, University of Utrecht, P.O. Box 80.089, 3508, Utrecht, TB, The Netherlands

    Gerard Tel

  3. Faculty of Mathematics and Physics, Charles University, Prague

    Jaroslav Pokorný

  4. Institute of Informatics and Software Engineering Faculty of Informatics and Information technologies, Slovak University of Technology, Ilkovičova 3, 842 16, Bratislava

    Mária Bieliková

Rights and permissions

Reprints and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Christodoulakis, M., Iliopoulos, C.S., Ardila, Y.J.P. (2006). Simple Algorithm for Sorting the Fibonacci String Rotations. In: Wiedermann, J., Tel, G., Pokorný, J., Bieliková, M., Štuller, J. (eds) SOFSEM 2006: Theory and Practice of Computer Science. SOFSEM 2006. Lecture Notes in Computer Science, vol 3831. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11611257_19

Download citation

  • DOI: https://doi.org/10.1007/11611257_19

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-31198-0

  • Online ISBN: 978-3-540-32217-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation