How to build billiard words using decimations

Jean-Pierre Borel

RAIRO - Theoretical Informatics and Applications (2010)

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

Abstract

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

How to cite

top

Borel, 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
  1. J-P. Allouche and J. Shallit, Automatic sequences: Theory and Applications. Cambridge University Press (2003).  Zbl1086.11015
  2. J. Berstel and P. Séébold, Sturmian words, in Algebraic combinatorics on words, edited by M. Lothaire, Cambridge University Press (2002).  Zbl0883.68104
  3. J-P. Borel, Opérations sur les mots de Christoffel. C.R. Acad. Sci. Paris325 (1997) 239–242.  
  4. J-P. Borel, Image homographique de mots de Christoffel. Bull. Belg. Math. Soc.8 (2001) 239–253.  
  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.  Zbl1227.68085
  6. J-P. Borel and C. Reutenauer, Palindromic factors of billiard words. Theoret. Comput. Sci.340 (2005) 334–348.  Zbl1078.68113
  7. A.M. Bruckstein, Self-similarity properties of digitized straight lines. Contemp. Math.119 (1991) 1–20.  Zbl0752.68063
  8. D. Crisp, W. Moran, A. Pollington and P. Shive, Substitution invariant cutting sequences. J. Théor. Nombres Bordeaux5 (1993) 123–137.  Zbl0786.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.  Zbl0889.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.  Zbl0456.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).  Zbl0613.10044
  14. C. Series, The geometry of Markoff numbers. Math. Intelligencer7 (1985) 20–29.  Zbl0566.10024

NotesEmbed ?

top

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.