Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-28T08:10:17.242Z Has data issue: false hasContentIssue false
  • English
  • Français

How to build billiard words using decimations

Published online by Cambridge University Press:  11 February 2010

Jean-Pierre Borel
Jean-Pierre Borel*
Affiliation:
XLim, UMR 6172, Université de Limoges – CNRS, 123 avenue Albert Thomas, 87060 Limoges Cedex, France; [email protected]
Get access

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.

Keywords

Decimations.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 44 , Issue 1: Special issue dedicated to the 12th "Journées Montoises d'Informatique Théorique" , January 2010 , pp. 59 - 77
Copyright
© EDP Sciences, 2010

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

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).
Borel, J-P., Opérations sur les mots de Christoffel. C.R. Acad. Sci. Paris 325 (1997) 239–242. CrossRef
Borel, J-P., 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.
Borel, J-P. and Reutenauer, C., Palindromic factors of billiard words. Theoret. Comput. Sci. 340 (2005) 334–348. CrossRef
Bruckstein, A.M., Self-similarity properties of digitized straight lines. Contemp. Math. 119 (1991) 1–20. CrossRef
Crisp, D., Moran, W., Pollington, A. and Shive, P., Substitution invariant cutting sequences. J. Théor. Nombres Bordeaux 5 (1993) 123–137. CrossRef
Freeman, H., On the encoding of arbitrary geometric configuration. IRE Trans. Electron. Comput. 10 (1961) 260–268. CrossRef
Justin, J. and Pirillo, G., Decimations and Sturmian words. RAIRO-Theor. Inf. Appl. 31 (1997) 271–290. CrossRef
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).
Series, C., The geometry of Markoff numbers. Math. Intelligencer 7 (1985) 20–29. CrossRef