On Christoffel classes

Jean-Pierre Borel; Christophe Reutenauer

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2006)

  • Volume: 40, Issue: 1, page 15-27
  • ISSN: 0988-3754

Abstract

top
We characterize conjugation classes of Christoffel words (equivalently of standard words) by the number of factors. We give several geometric proofs of classical results on these words and sturmian words.

How to cite

top

Borel, Jean-Pierre, and Reutenauer, Christophe. "On Christoffel classes." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 40.1 (2006): 15-27. <http://eudml.org/doc/245130>.

@article{Borel2006,
abstract = {We characterize conjugation classes of Christoffel words (equivalently of standard words) by the number of factors. We give several geometric proofs of classical results on these words and sturmian words.},
author = {Borel, Jean-Pierre, Reutenauer, Christophe},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {words; Christoffel; sturmian; conjugation; geometric; Christoffel word; Sturmian words},
language = {eng},
number = {1},
pages = {15-27},
publisher = {EDP-Sciences},
title = {On Christoffel classes},
url = {http://eudml.org/doc/245130},
volume = {40},
year = {2006},
}

TY - JOUR
AU - Borel, Jean-Pierre
AU - Reutenauer, Christophe
TI - On Christoffel classes
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2006
PB - EDP-Sciences
VL - 40
IS - 1
SP - 15
EP - 27
AB - We characterize conjugation classes of Christoffel words (equivalently of standard words) by the number of factors. We give several geometric proofs of classical results on these words and sturmian words.
LA - eng
KW - words; Christoffel; sturmian; conjugation; geometric; Christoffel word; Sturmian words
UR - http://eudml.org/doc/245130
ER -

References

top
  1. [1] J.-P. Allouche and J. Shallit, Automatic sequences. Cambridge (2003). Zbl1086.11015MR1997038
  2. [2] J. Berstel, Tracé de droites, fractions continues et morphismes itérés, in M. Lothaire, Mots, mélanges offerts M.-P. Schtzenberger, Hermès, Paris (1990) 298–309. 
  3. [3] J. Berstel and P. Séébold, Sturmian words, in M. Lothaire, Algebraic Combinatorics on Words, Cambridge University Press (2002) 45–110. Zbl0883.68104
  4. [4] J.-P. Borel and F. Laubie, Quelques mots sur la droite projective réelle. J. Théorie des Nombres de Bordeaux 5 (1993) 23–51. Zbl0839.11008
  5. [5] J. Berstel and A. de Luca, Sturmian words, Lyndon words and trees. Theor. Comput. Sci. 178 (1997) 171–2003. Zbl0901.68155
  6. [6] E.B. Christoffel, Observatio arithmetica. Annali di Matematica 6 (1875) 148–152. JFM06.0136.03
  7. [7] W.-F. Chuan, α -words and factors of characteristic sequences. Discrete Math. 177 (1997) 33–50. Zbl0890.68108
  8. [8] W.-F. Chuan, Characterizations of α -words, moments, and determinants. Fibonacci Quart. 41 (2003) 194–208. Zbl1048.11018
  9. [9] W.-F. Chuan, Moments of conjugacy classes of binary words. Theor. Comput. Sci. 310 (2004) 273–285. Zbl1098.68099
  10. [10] W.-F. Chuan, Factors of characteristic words of irrational numbers. Preprint. Zbl1087.68078MR2141220
  11. [11] H. Cohn, Markoff forms and primitive words. Math. Ann. 196 (1972) 8–22. Zbl0227.10018
  12. [12] A. de Luca, Sturmian words: structure, combinatorics, and their arithmetics. Theor. Comput. Sci. 183 (1997) 45–82. Zbl0911.68098
  13. [13] A. de Luca and F. Mignosi, On some combinatorial properties of Sturmian words. Theor. Compt. Sci. 136 (1994) 361–385. Zbl0874.68245
  14. [14] S. Mantaci, A. Restivo and M. Sciortino, Burrows-Wheeler transform and Sturmian words. Inform. Proc. Lett. 86 (2003) 241–246. Zbl1162.68511
  15. [15] G. Pirillo, A new characteristic property of the palindrome prefixes of a standard sturmian word. Sém. Lothar. Combin. 43 (1999) 1–3. Zbl0941.68101
  16. [16] G. Pirillo, A curious characteristic property of standard Sturmian word, in Algebraic Combinatorics, Computer Science, edited by H. Crapo and D. Senato. Springer (2001) 541–546. Zbl0966.68167

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.