How to build billiard words using decimations
Borel, Jean-Pierre
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 44 (2010), p. 59-77 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

We present two methods based on decimation for computing finite billiard words on any finite alphabet. The first method computes finite billiard words by iteration of some transformation on words. The number of iterations is explicitly bounded. The second one gives a direct formula for the billiard words. Some results remain true for infinite standard sturmian words, but cannot be used for computation as they only are limit results.

Publié le : 2010-01-01
DOI : https://doi.org/10.1051/ita/2010005
Classification:  68R15,  68Q68 
@article{ITA_2010__44_1_59_0,
     author = {Borel, Jean-Pierre},
     title = {How to build billiard words using decimations},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {44},
     year = {2010},
     pages = {59-77},
     doi = {10.1051/ita/2010005},
     mrnumber = {2604935},
     zbl = {1184.68369},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2010__44_1_59_0}
}

Borel, Jean-Pierre. How to build billiard words using decimations. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 44 (2010) pp. 59-77. doi : 10.1051/ita/2010005. http://gdmltest.u-ga.fr/item/ITA_2010__44_1_59_0/

[1] J-P. Allouche and J. Shallit, Automatic sequences: Theory and Applications. Cambridge University Press (2003). | Zbl 1086.11015

[2] J. Berstel and P. Séébold, Sturmian words, in Algebraic combinatorics on words, edited by M. Lothaire, Cambridge University Press (2002).

[3] J-P. Borel, Opérations sur les mots de Christoffel. C.R. Acad. Sci. Paris 325 (1997) 239-242. | Zbl 0887.11013

[4] J-P. Borel, Image homographique de mots de Christoffel. Bull. Belg. Math. Soc. 8 (2001) 239-253. | Zbl 0994.68101

[5] J-P. Borel, Complexity of degenerated three dimensional billiard words, in DLT 2006, edited by H. Ibarra and Z. Dang. Lect. Notes Comput. Sci. 4036 (2006) 386-396. | Zbl pre05533843

[6] J-P. Borel and C. Reutenauer, Palindromic factors of billiard words. Theoret. Comput. Sci. 340 (2005) 334-348. | Zbl 1078.68113

[7] A.M. Bruckstein, Self-similarity properties of digitized straight lines. Contemp. Math. 119 (1991) 1-20. | Zbl 0752.68063

[8] D. Crisp, W. Moran, A. Pollington and P. Shive, Substitution invariant cutting sequences. J. Théor. Nombres Bordeaux 5 (1993) 123-137. | Numdam | Zbl 0786.11041

[9] H. Freeman, On the encoding of arbitrary geometric configuration. IRE Trans. Electron. Comput. 10 (1961) 260-268.

[10] J. Justin and G. Pirillo, Decimations and Sturmian words. RAIRO-Theor. Inf. Appl. 31 (1997) 271-290. | Numdam | Zbl 0889.68090

[11] J. Koplowitz, On the performance of Chain Codes for Quantization of Line Drawings. IEEE Trans Pattern Anal. Machine Intell. PAMI-3 (1981) 357-393. | Zbl 0456.68117

[12] B. Parvaix, Contribution à l'étude des suites sturmiennes, Ph.D. Thesis, Univ. Limoges, France (1998).

[13] G. Rauzy, Mots infinis en arithmétique, in Automata on Infinite Words, edited by M. Nivat and D. Perrin. Lect. Notes Comput. Sci. 192 (1985). | Zbl 0613.10044

[14] C. Series, The geometry of Markoff numbers. Math. Intelligencer 7 (1985) 20-29. | Zbl 0566.10024