How to build billiard words using decimations
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 44 (2010) no. 1, pp. 59-77.

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.

DOI : 10.1051/ita/2010005
Classification : 68R15, 68Q68
Mots-clés : decimations 
@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},
     pages = {59--77},
     publisher = {EDP-Sciences},
     volume = {44},
     number = {1},
     year = {2010},
     doi = {10.1051/ita/2010005},
     mrnumber = {2604935},
     zbl = {1184.68369},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita/2010005/}
}
TY  - JOUR
AU  - Borel, Jean-Pierre
TI  - How to build billiard words using decimations
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2010
SP  - 59
EP  - 77
VL  - 44
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita/2010005/
DO  - 10.1051/ita/2010005
LA  - en
ID  - ITA_2010__44_1_59_0
ER  - 
%0 Journal Article
%A Borel, Jean-Pierre
%T How to build billiard words using decimations
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2010
%P 59-77
%V 44
%N 1
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita/2010005/
%R 10.1051/ita/2010005
%G en
%F 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) no. 1, pp. 59-77. doi : 10.1051/ita/2010005. http://www.numdam.org/articles/10.1051/ita/2010005/

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

[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

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

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

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

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

[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

[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

[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

[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

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

Cité par Sources :