On Christoffel classes

Jean-Pierre Borel; Christophe Reutenauer

RAIRO - Theoretical Informatics and Applications (2010)

  • 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 40.1 (2010): 15-27. <http://eudml.org/doc/92786>.

@article{Borel2010,
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},
keywords = {Words; Christoffel; sturmian; conjugation; geometric.; Christoffel word; Sturmian words},
language = {eng},
month = {3},
number = {1},
pages = {15-27},
publisher = {EDP Sciences},
title = {On Christoffel classes},
url = {http://eudml.org/doc/92786},
volume = {40},
year = {2010},
}

TY - JOUR
AU - Borel, Jean-Pierre
AU - Reutenauer, Christophe
TI - On Christoffel classes
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
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/92786
ER -

References

top
  1. J.-P. Allouche and J. Shallit, Automatic sequences. Cambridge (2003).  
  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. J. Berstel and P. Séébold, Sturmian words, in M. Lothaire, Algebraic Combinatorics on Words, Cambridge University Press (2002) 45–110.  
  4. J.-P. Borel and F. Laubie, Quelques mots sur la droite projective réelle. J. Théorie des Nombres de Bordeaux5 (1993) 23–51.  
  5. J. Berstel and A. de Luca, Sturmian words, Lyndon words and trees. Theor. Comput. Sci.178 (1997) 171–2003.  
  6. E.B. Christoffel, Observatio arithmetica. Annali di Matematica6 (1875) 148–152.  
  7. W.-F. Chuan, α-words and factors of characteristic sequences. Discrete Math.177 (1997) 33–50.  
  8. W.-F. Chuan, Characterizations of α-words, moments, and determinants. Fibonacci Quart.41 (2003) 194–208.  
  9. W.-F. Chuan, Moments of conjugacy classes of binary words. Theor. Comput. Sci.310 (2004) 273–285.  
  10. W.-F. Chuan, Factors of characteristic words of irrational numbers. Preprint.  
  11. H. Cohn, Markoff forms and primitive words. Math. Ann.196 (1972) 8–22.  
  12. A. de Luca, Sturmian words: structure, combinatorics, and their arithmetics. Theor. Comput. Sci.183 (1997) 45–82.  
  13. A. de Luca and F. Mignosi, On some combinatorial properties of Sturmian words. Theor. Compt. Sci.136 (1994) 361–385.  
  14. S. Mantaci, A. Restivo and M. Sciortino, Burrows-Wheeler transform and Sturmian words. Inform. Proc. Lett.86 (2003) 241–246.  
  15. G. Pirillo, A new characteristic property of the palindrome prefixes of a standard sturmian word. Sém. Lothar. Combin.43 (1999) 1–3.  
  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.  

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.