On Christoffel classes
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 1, pp. 15-27.

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.

DOI : 10.1051/ita:2005038
Classification : 68R15
Mots clés : words, Christoffel, sturmian, conjugation, geometric
@article{ITA_2006__40_1_15_0,
     author = {Borel, Jean-Pierre and Reutenauer, Christophe},
     title = {On {Christoffel} classes},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {15--27},
     publisher = {EDP-Sciences},
     volume = {40},
     number = {1},
     year = {2006},
     doi = {10.1051/ita:2005038},
     mrnumber = {2197281},
     zbl = {1085.68116},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita:2005038/}
}
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
SP  - 15
EP  - 27
VL  - 40
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2005038/
DO  - 10.1051/ita:2005038
LA  - en
ID  - ITA_2006__40_1_15_0
ER  - 
%0 Journal Article
%A Borel, Jean-Pierre
%A Reutenauer, Christophe
%T On Christoffel classes
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2006
%P 15-27
%V 40
%N 1
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita:2005038/
%R 10.1051/ita:2005038
%G en
%F ITA_2006__40_1_15_0
Borel, Jean-Pierre; Reutenauer, Christophe. On Christoffel classes. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 1, pp. 15-27. doi : 10.1051/ita:2005038. http://www.numdam.org/articles/10.1051/ita:2005038/

[1] J.-P. Allouche and J. Shallit, Automatic sequences. Cambridge (2003). | MR | Zbl

[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 Bordeaux 5 (1993) 23-51. | Numdam | Zbl

[5] J. Berstel and A. De Luca, Sturmian words, Lyndon words and trees. Theor. Comput. Sci. 178 (1997) 171-2003. | Zbl

[6] E.B. Christoffel, Observatio arithmetica. Annali di Matematica 6 (1875) 148-152. | JFM

[7] W.-F. Chuan, α-words and factors of characteristic sequences. Discrete Math. 177 (1997) 33-50. | Zbl

[8] W.-F. Chuan, Characterizations of α-words, moments, and determinants. Fibonacci Quart. 41 (2003) 194-208. | Zbl

[9] W.-F. Chuan, Moments of conjugacy classes of binary words. Theor. Comput. Sci. 310 (2004) 273-285. | Zbl

[10] W.-F. Chuan, Factors of characteristic words of irrational numbers. Preprint. | MR | Zbl

[11] H. Cohn, Markoff forms and primitive words. Math. Ann. 196 (1972) 8-22. | Zbl

[12] A. De Luca, Sturmian words: structure, combinatorics, and their arithmetics. Theor. Comput. Sci. 183 (1997) 45-82. | Zbl

[13] A. De Luca and F. Mignosi, On some combinatorial properties of Sturmian words. Theor. Compt. Sci. 136 (1994) 361-385. | Zbl

[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. | Zbl

[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. | Zbl

Cité par Sources :