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
topHow 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).
- J. Berstel and P. Séébold, Sturmian words, in Algebraic combinatorics on words, edited by M. Lothaire, Cambridge University Press (2002).
- 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.
- J-P. Borel and C. Reutenauer, Palindromic factors of billiard words. Theoret. Comput. Sci.340 (2005) 334–348.
- A.M. Bruckstein, Self-similarity properties of digitized straight lines. Contemp. Math.119 (1991) 1–20.
- D. Crisp, W. Moran, A. Pollington and P. Shive, Substitution invariant cutting sequences. J. Théor. Nombres Bordeaux5 (1993) 123–137.
- 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.
- J. Koplowitz, On the performance of Chain Codes for Quantization of Line Drawings. IEEE Trans Pattern Anal. Machine Intell.PAMI-3 (1981) 357–393.
- 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).
- C. Series, The geometry of Markoff numbers. Math. Intelligencer7 (1985) 20–29.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.