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.
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://archive.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://archive.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://archive.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://archive.numdam.org/articles/10.1051/ita/2010005/
[1] Automatic sequences: Theory and Applications. Cambridge University Press (2003). | Zbl
and ,[2] Sturmian words, in Algebraic combinatorics on words, edited by M. Lothaire, Cambridge University Press (2002).
and ,[3] Opérations sur les mots de Christoffel. C.R. Acad. Sci. Paris 325 (1997) 239-242. | Zbl
,[4] Image homographique de mots de Christoffel. Bull. Belg. Math. Soc. 8 (2001) 239-253. | Zbl
,[5] 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] Palindromic factors of billiard words. Theoret. Comput. Sci. 340 (2005) 334-348. | Zbl
and ,[7] Self-similarity properties of digitized straight lines. Contemp. Math. 119 (1991) 1-20. | Zbl
,[8] Substitution invariant cutting sequences. J. Théor. Nombres Bordeaux 5 (1993) 123-137. | Numdam | Zbl
, , and ,[9] On the encoding of arbitrary geometric configuration. IRE Trans. Electron. Comput. 10 (1961) 260-268.
,[10] Decimations and Sturmian words. RAIRO-Theor. Inf. Appl. 31 (1997) 271-290. | Numdam | Zbl
and ,[11] On the performance of Chain Codes for Quantization of Line Drawings. IEEE Trans Pattern Anal. Machine Intell. PAMI-3 (1981) 357-393. | Zbl
,[12] Contribution à l'étude des suites sturmiennes, Ph.D. Thesis, Univ. Limoges, France (1998).
,[13] 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] The geometry of Markoff numbers. Math. Intelligencer 7 (1985) 20-29. | Zbl
,Cité par Sources :