SpringerLink
Log in

Sturmian and Episturmian Words

(A Survey of Some Recent Results)

  • Conference paper
Algebraic Informatics (CAI 2007)

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

Included in the following conference series:

Abstract

This survey paper contains a description of some recent results concerning Sturmian and episturmian words, with particular emphasis on central words. We list fourteen characterizations of central words. We give the characterizations of Sturmian and episturmian words by lexicographic ordering, we show how the Burrows-Wheeler transform behaves on Sturmian words. We mention results on balanced episturmian words. We give a description of the compact suffix automaton of central Sturmian words.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
EUR 29.95
Price includes VAT (Germany)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
EUR 42.79
Price includes VAT (Germany)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
EUR 53.49
Price includes VAT (Germany)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

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. Klette, R., Rosenfeld, A.: Digital straightness—a review. Discrete Appl. Math. 139, 197–230 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  2. Morse, M., Hedlund, G.A.: Symbolic dynamics II. Sturmian trajectories. Amer. J. Math. 62, 1–42 (1940)

    Article  MATH  MathSciNet  Google Scholar 

  3. Berstel, J., Boasson, L., Carton, O., Fagnot, I.: A first investigation of Sturmian trees. In: Thomas, W., Weil, P. (eds.) STACS 2007. LNCS, vol. 4393, pp. 73–84. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  4. de Luca, A., De Luca, A.: Pseudopalindrome closure operators in free monoids. Theoret. Comput. Sci. 362(1-3), 282–300 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  5. Droubay, X., Justin, J., Pirillo, G.: Epi-Sturmian words and some constructions of de Luca and Rauzy. Theoret. Comput. Sci. 255(1-2), 539–553 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  6. Justin, J., Pirillo, G.: On a characteristic property of Arnoux-Rauzy sequences. Theor. Inform. Appl. 36(4), 385–388 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  7. Justin, J., Pirillo, G.: Episturmian words and episturmian morphisms. Theoret. Comput. Sci. 276(1-2), 281–313 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  8. Justin, J.: Episturmian words and morphisms (results and conjectures). In: Crapo, H., Senato, D. (eds.) Algebraic Combinatorics and Computer Science, pp. 533–539. Springer, Heidelberg (2001)

    Google Scholar 

  9. Arnoux, P., Rauzy, G.: Représentation géométrique de suites de complexité 2n + 1. Bull. Soc. Math. France 119, 199–215 (1991)

    MATH  MathSciNet  Google Scholar 

  10. Coven, E.M., Hedlund, G.A.: Sequences with minimal block growth. Math. Systems Theory 7, 138–153 (1973)

    Article  MATH  MathSciNet  Google Scholar 

  11. Allouche, J.P., Baake, M., Cassaigne, J., Damanik, D.: Palindrome complexity. Theoret. Comput. Sci. 292(1), 9–31 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  12. Baláži, P., Masáková, Z., Pelantová, E.: Factor versus palindromic complexity of uniformly recurrent infinite words. Theoret. Comput. Sci. 380, 266–275 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  13. Droubay, X., Pirillo, G.: Palindromes and Sturmian words. Theoret. Comput. Sci. 223(1-2), 73–85 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  14. Damanik, D., Zamboni, L.Q.: Combinatorial properties of Arnoux-Rauzy subshifts and applications to Schrödinger operators. Rev. Math. Phys. 15(7), 745–763 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  15. Avgustinovich, S.V., Fon-Der-Flaas, D.G., Frid, A.E.: Arithmetical complexity of infinite words. In: Words, Languages and Combinatorics. Proc. 3rd Conf. Words, Languages and Combinatorics, Kyoto, March 2000, vol. III, pp. 51–62. World Scientific, Singapore (2003)

    Chapter  Google Scholar 

  16. Cassaigne, J., Frid, A.E.: On the arithmetical complexity of Sturmian words. Theoret. Comput. Sci. 380, 304–316 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  17. Avgustinovich, S.V., Cassaigne, J., Frid, A.E.: Sequences of low arithmetical complexity. Theor. Inform. Appl. 40(4), 569–582 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  18. Kamae, T., Zamboni, L.Q.: Maximal pattern complexity for discrete systems. Ergodic Theory Dynam. Systems 22(4), 1201–1214 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  19. Kamae, T., Rao, H., Tan, B., Xue, Y.M.: Language structure of pattern Sturmian words. Discrete Math. 306(15), 1651–1668 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  20. Kamae, T., Rao, H.: Maximal pattern complexity of words over l letters. European J. Combin. 27(1), 125–137 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  21. Nakashima, I., Tamura, J.I., Yasutomi, S.I.: Modified complexity and ∗-Sturmian word. Proc. Japan Acad. Ser. A Math. Sci. 75(3), 26–28 (1999)

    MATH  MathSciNet  Google Scholar 

  22. Nakashima, I., Tamura, J.I., Yasutomi, S.I.: *-Sturmian words and complexity. J. Theor. Nombres Bordeaux 15(3), 767–804 (2003)

    MATH  MathSciNet  Google Scholar 

  23. de Luca, A.: Sturmian words: structure, combinatorics, and their arithmetics. Theoret. Comput. Sci. 183(1), 45–82 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  24. de Luca, A.: Combinatorics of standard Sturmian words. In: Mycielski, J., Rozenberg, G., Salomaa, A. (eds.) Structures in Logic and Computer Science. LNCS, vol. 1261, pp. 249–267. Springer, Heidelberg (1997)

    Google Scholar 

  25. Risley, R., Zamboni, L.Q.: A generalization of Sturmian sequences: combinatorial structure and transcendence. Acta Arith. 95, 167–184 (2000)

    MATH  MathSciNet  Google Scholar 

  26. Glen, A.: Powers in a class of \({\cal a}\)-strict standard episturmian words. Theoret. Comput. Sci. 380, 330–354 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  27. Tan, B., Wen, Z.Y.: Some properties of the Tribonacci sequence. European J. Combin. (2007)

    Google Scholar 

  28. Chekhova, N., Hubert, P., Messaoudi, A.: Propriétés combinatoires, ergodiques et arithmétiques de la substitution de Tribonacci. J. Theor. Nombres Bordeaux 13(2), 371–394 (2001)

    MATH  MathSciNet  Google Scholar 

  29. Lothaire, M.: Applied Combinatorics on Words. Encyclopedia of Mathematics and its Applications, vol. 105. Cambridge University Press, Cambridge (2005)

    MATH  Google Scholar 

  30. Series, C.: The geometry of Markoff numbers. Math. Intelligencer 7(3), 20–29 (1985)

    MATH  MathSciNet  Google Scholar 

  31. Berthé, V., Ei, H., Ito, S., Rao, H.: Invertible substitutions and Sturmian words: an application to Rauzy fractals. Theor. Inform. Appl. (to appear, 2007)

    Google Scholar 

  32. Lothaire, M.: Algebraic Combinatorics on Words. Encyclopedia of Mathematics and its Applications, vol. 90. Cambridge University Press, Cambridge (2002)

    MATH  Google Scholar 

  33. Pytheas Fogg, N.: Substitutions in dynamics, arithmetics and combinatorics. In: Berthé, V., Ferenczi, S., Mauduit, C., Siegel, A. (eds.) Lecture Notes in Mathematics, vol. 1794, Springer, Heidelberg (2002)

    Google Scholar 

  34. Christoffel, E.B.: Observatio arithmetica. Annali di Mathematica 6, 145–152 (1875)

    Google Scholar 

  35. Pirillo, G.: A curious characteristic property of standard Sturmian words. In: Crapo, H., Senato, D. (eds.) Algebraic Combinatorics and Computer Science. A tribute to Gian-Carlo Rota, pp. 541–546. Springer, Heidelberg (2001)

    Google Scholar 

  36. de Luca, A., Mignosi, F.: Some combinatorial properties of Sturmian words. Theoret. Comput. Sci. 136(2), 361–385 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  37. Borel, J.P., Reutenauer, C.: Palindromic factors of billiard words. Theoret. Comput. Sci. 340(2), 334–348 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  38. de Luca, A., De Luca, A.: Combinatorial properties of Sturmian palindromes. Internat. J. Found. Comput. Sci. 17(3), 557–573 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  39. Carpi, A., de Luca, A.: Codes of central Sturmian words. Theoret. Comput. Sci. 340(2), 220–239 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  40. Berstel, J., de Luca, A.: Sturmian words, Lyndon words and trees. Theoret. Comput. Sci. 178(1-2), 171–203 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  41. Berthé, V., de Luca, A., Reutenauer, C.: On an involution of Christoffel words and Sturmian morphisms. In: European J. Combinatorics (in press, 2007)

    Google Scholar 

  42. Chuan, W.F.: Moments of conjugacy classes of binary words. Theoret. Comput. Sci. 310(1-3), 273–285 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  43. Jenkinson, O., Zamboni, L.Q.: Characterisations of balanced words via orderings. Theoret. Comput. Sci. 310(1-3), 247–271 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  44. de Luca, A., De Luca, A.: Some characterizations of finite Sturmian words. Theoret. Comput. Sci. 356(1-2), 118–125 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  45. Fagnot, I., Vuillon, L.: Generalized balances in Sturmian words. Discrete Appl. Math. 121(1-3), 83–101 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  46. Cassaigne, J., Ferenczi, S., Zamboni, L.Q.: Imbalances in Arnoux-Rauzy sequences. Ann. Inst. Fourier (Grenoble) 50(4), 1265–1276 (2000)

    MATH  MathSciNet  Google Scholar 

  47. Lipatov, E.P.: A classification of binary collections and properties of homogeneity classes. Problemy Kibernet 39, 67–84 (1982)

    MathSciNet  Google Scholar 

  48. Mignosi, F.: On the number of factors of Sturmian words. Theoret. Comput. Sci. 82(1), 71–84 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  49. Berstel, J., Pocchiola, M.: A geometric proof of the enumeration formula for Sturmian words. Internat. J. Algebra Comput. 3(3), 349–355 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  50. Berstel, J., Pocchiola, M.: Random generation of finite Sturmian words. In: Proceedings of the 5th Conference on Formal Power Series and Algebraic Combinatorics (Florence, 1993), vol. 153, pp. 29–39 (1996)

    Google Scholar 

  51. Berenstein, C.A., Lavine, D.: On the number of digital straight line segments. IEEE Trans. Pattern Anal. Mach. Intell. 10(6), 880–887 (1988)

    Article  MATH  Google Scholar 

  52. Koplowitz, J., Lindenbaum, M., Bruckstein, A.M.: The number of digital straight lines on an n×n grid. IEEE Transactions on Information Theory 36(1), 192–197 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  53. Heinis, A.: On low-complexity bi-infinite words and their factors. J. Theor. Nombres Bordeaux 13(2), 421–442 (2001)

    MATH  MathSciNet  Google Scholar 

  54. Tarannikov, Y.: On the bounds for the number of ℓ-balanced words. Technical report, Mech. & Math. Department, Moscow State University (2007)

    Google Scholar 

  55. Mignosi, F., Zamboni, L.Q.: On the number of Arnoux-Rauzy words. Boolean Calculus of Differences 101(2), 121–129 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  56. Paquin, G., Vuillon, L.: A characterization of balanced episturmian sequences. Electronic J. Combinatorics 14(1) R33, pages 12 (2007)

    Google Scholar 

  57. Glen, A., Justin, J., Pirillo, G.: Characterizations of finite and infinite episturmian words via lexicographic orderings. European Journal of Combinatorics (2007)

    Google Scholar 

  58. Pirillo, G.: Morse and Hedlund’s skew Sturmian words revisited. Annals Combinatorics  (to appear, 2007)

    Google Scholar 

  59. Gan, S.: Sturmian sequences and the lexicographic world. Proc. Amer. Math. Soc. (electronic) 129, 1445–1451 (2001)

    Google Scholar 

  60. Glen, A.: A characterization of fine words over a finite alphabet. Theoret. Comput. Sci. CANT conference, Liege, Belgium, May 8-19, 2007, 8–19 (to appear, 2007)

    Google Scholar 

  61. Pirillo, G.: Inequalities characterizing standard Sturmian and episturmian words. Theoret. Comput. Sci. 341, 276–292 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  62. Burrows, M., Wheeler, D.J.: A block sorting data compression algorithm. Technical report, Digital System Research Center (1994)

    Google Scholar 

  63. Gessel, I., Reutenauer, C.: Counting permutations with given cycle structure and descent set. J. Comb. Theory A 64, 189–215 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  64. Crochemore, M., Désarménien, J., Perrin, D.: A note on the Burrows-Wheeler transformation. Theoret. Comput. Sci. 332, 567–572 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  65. Mantaci, S., Restivo, A., Sciortino, M.: Burrows Wheeler transform and Sturmian words. Inform. Proc. Letters 86, 241–246 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  66. Mantaci, S., Restivo, A., Rosone, G., Sciortino, M.: An extension of the Burrows Wheeler transform. Theoret. Comput. Sci. (2007)

    Google Scholar 

  67. Rytter, W.: The structure of subword graphs and suffix trees of Fibonacci words. Theoret. Comput. Sci. 363(2), 211–223 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  68. Epifanio, C., Mignosi, F., Shallit, J., Venturini, I.: On Sturmian graphs. Discrete Appl. Math 155, 1014–1030 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  69. Blumer, A., Blumer, J.A., Haussler, D., Ehrenfeucht, A., Chen, M.T., Seiferas, J.I.: The smallest automaton recognizing the subwords of a text (Special issue: Eleventh international colloquium on automata, languages and programming (Antwerp, 1984)). Theoret. Comput. Sci. 40(1), 31–55 (1985)

    Article  MATH  MathSciNet  Google Scholar 

  70. Crochemore, M., Rytter, W.: Jewels of stringology. World Scientific Publishing Co. Inc, River Edge, NJ (2003)

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut Gaspard Monge, Université Paris-Est, Marne-la-Vallée, France

    Jean Berstel

Authors
  1. Jean Berstel
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Symeon Bozapalidis George Rahonis

Rights and permissions

Reprints and permissions

Copyright information

© 2007 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Berstel, J. (2007). Sturmian and Episturmian Words. In: Bozapalidis, S., Rahonis, G. (eds) Algebraic Informatics. CAI 2007. Lecture Notes in Computer Science, vol 4728. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-75414-5_2

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-75414-5_2

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-75413-8

  • Online ISBN: 978-3-540-75414-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation