# How to build billiard words using decimations

RAIRO - Theoretical Informatics and Applications (2010)

- Volume: 44, Issue: 1, page 59-77
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topBorel, Jean-Pierre. "How to build billiard words using decimations." RAIRO - Theoretical Informatics and Applications 44.1 (2010): 59-77. <http://eudml.org/doc/250768>.

@article{Borel2010,

abstract = {
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.
},

author = {Borel, Jean-Pierre},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Decimations.; decimations; infinite standard Sturmian words},

language = {eng},

month = {2},

number = {1},

pages = {59-77},

publisher = {EDP Sciences},

title = {How to build billiard words using decimations},

url = {http://eudml.org/doc/250768},

volume = {44},

year = {2010},

}

TY - JOUR

AU - Borel, Jean-Pierre

TI - How to build billiard words using decimations

JO - RAIRO - Theoretical Informatics and Applications

DA - 2010/2//

PB - EDP Sciences

VL - 44

IS - 1

SP - 59

EP - 77

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

LA - eng

KW - Decimations.; decimations; infinite standard Sturmian words

UR - http://eudml.org/doc/250768

ER -

## References

top- J-P. Allouche and J. Shallit, Automatic sequences: Theory and Applications. Cambridge University Press (2003). Zbl1086.11015
- J. Berstel and P. Séébold, Sturmian words, in Algebraic combinatorics on words, edited by M. Lothaire, Cambridge University Press (2002). Zbl0883.68104
- J-P. Borel, Opérations sur les mots de Christoffel. C.R. Acad. Sci. Paris325 (1997) 239–242.
- J-P. Borel, Image homographique de mots de Christoffel. Bull. Belg. Math. Soc.8 (2001) 239–253.
- 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. Zbl1227.68085
- J-P. Borel and C. Reutenauer, Palindromic factors of billiard words. Theoret. Comput. Sci.340 (2005) 334–348. Zbl1078.68113
- A.M. Bruckstein, Self-similarity properties of digitized straight lines. Contemp. Math.119 (1991) 1–20. Zbl0752.68063
- D. Crisp, W. Moran, A. Pollington and P. Shive, Substitution invariant cutting sequences. J. Théor. Nombres Bordeaux5 (1993) 123–137. Zbl0786.11041
- H. Freeman, On the encoding of arbitrary geometric configuration. IRE Trans. Electron. Comput.10 (1961) 260–268.
- J. Justin and G. Pirillo, Decimations and Sturmian words. RAIRO-Theor. Inf. Appl.31 (1997) 271–290. Zbl0889.68090
- J. Koplowitz, On the performance of Chain Codes for Quantization of Line Drawings. IEEE Trans Pattern Anal. Machine Intell.PAMI-3 (1981) 357–393. Zbl0456.68117
- B. Parvaix, Contribution à l'étude des suites sturmiennes, Ph.D. Thesis, Univ. Limoges, France (1998).
- 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). Zbl0613.10044
- C. Series, The geometry of Markoff numbers. Math. Intelligencer7 (1985) 20–29. Zbl0566.10024

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.