We establish a relationship between the word complexity and the number of generalized diagonals for a polygonal billiard. We conclude that in the rational case the complexity function has cubic upper and lower bounds. In the tiling case the complexity has cubic asymptotic growth.
Nous établissons un lien entre la fonction de complexité et le nombre de diagonales généralisées pour un billard polygonal. Dans le cas où le billard est rationnel, la fonction de complexité est comprise entre deux polynômes cubiques; elle a une asymptotique cubique lorsque le polygone pave le plan.
Keywords: complexity, polygonal billiards, generalized diagonals, bispecial words
Mot clés : complexité, billards polygonaux, diagonales généralisées, mots bispéciaux
Cassaigne, J. 1; Hubert, Pascal 1; Troubetzkoy, Serge 2
@article{AIF_2002__52_3_835_0, author = {Cassaigne, J. and Hubert, Pascal and Troubetzkoy, Serge}, title = {Complexity and growth for polygonal billiards}, journal = {Annales de l'Institut Fourier}, pages = {835--847}, publisher = {Association des Annales de l{\textquoteright}institut Fourier}, volume = {52}, number = {3}, year = {2002}, doi = {10.5802/aif.1903}, zbl = {01794816}, mrnumber = {1907389}, language = {en}, url = {https://aif.centre-mersenne.org/articles/10.5802/aif.1903/} }
TY - JOUR AU - Cassaigne, J. AU - Hubert, Pascal AU - Troubetzkoy, Serge TI - Complexity and growth for polygonal billiards JO - Annales de l'Institut Fourier PY - 2002 SP - 835 EP - 847 VL - 52 IS - 3 PB - Association des Annales de l’institut Fourier UR - https://aif.centre-mersenne.org/articles/10.5802/aif.1903/ DO - 10.5802/aif.1903 LA - en ID - AIF_2002__52_3_835_0 ER -
%0 Journal Article %A Cassaigne, J. %A Hubert, Pascal %A Troubetzkoy, Serge %T Complexity and growth for polygonal billiards %J Annales de l'Institut Fourier %D 2002 %P 835-847 %V 52 %N 3 %I Association des Annales de l’institut Fourier %U https://aif.centre-mersenne.org/articles/10.5802/aif.1903/ %R 10.5802/aif.1903 %G en %F AIF_2002__52_3_835_0
Cassaigne, J.; Hubert, Pascal; Troubetzkoy, Serge. Complexity and growth for polygonal billiards. Annales de l'Institut Fourier, Volume 52 (2002) no. 3, pp. 835-847. doi : 10.5802/aif.1903. https://aif.centre-mersenne.org/articles/10.5802/aif.1903/
[BKM] Billiards in polygons, Ann. Prob., Volume 6 (1978), pp. 532-540 | DOI | MR | Zbl
[BP] A geometric proof of the enumeration formula for Sturmian words, J. Alg. Comp., Volume 3 (1993), pp. 349-355 | DOI | MR | Zbl
[C] Complexité et facteurs spéciaux, Bull. Belgian Math. Soc., Volume 4 (1997), pp. 67-88 | EuDML | MR | Zbl
[CT] Ergodicity of billiards in polygons with pockets, Nonlinearity, Volume 11 (1998), pp. 1095-1102 | DOI | MR | Zbl
[GKT] Local instability of orbits in polygonal and polyhedral billiards, Comm. Math. Phys., Volume 169 (1995), pp. 463-473 | DOI | MR | Zbl
[Gu1] Billiards in polygons, Physica D, Volume 19 (1986), pp. 311-333 | DOI | MR | Zbl
[Gu2] Billiards in polygons: survey of recent results, J. Stat. Phys., Volume 174 (1995), pp. 43-56 | MR | Zbl
[GuH] Topological entropy of generalized interval exchanges, Bull. AMS, Volume 32 (1995), pp. 50-57 | DOI | MR | Zbl
[GuT] Directional flows and strong recurrence for polygonal billiards, Proceedings of the International Congress of Dynamical Systems, Montevideo, Uruguay (Pitman Research Notes in Math.), Volume 362 (1996) | Zbl
[H] Dynamique symbolique des billards polygonaux rationnels (1995) (Thèse, Université d'Aix-Marseille II)
[H1] Complexité des suites définies par des billards rationnels, Bull. Soc. Math. France, Volume 123 (1995), pp. 257-270 | Numdam | MR | Zbl
[H2] Propriétés combinatoires des suites définies par le billard dans les triangles pavants, Theoret. Comput. Sci., Volume 164 (1996), pp. 165-183 | DOI | MR | Zbl
[HW] An introduction to the theory of numbers, Oxford Univ. Press, 1964 | MR | Zbl
[K] The growth rate for the number of singular and periodic orbits for a polygonal billiard, Comm. Math. Phys., Volume 111 (1987), pp. 151-160 | DOI | MR | Zbl
[M1] The growth rate of a quadratic differential, Ergod. Th. Dyn. Sys., Volume 10 (1990), pp. 151-176 | MR | Zbl
[M2] Lower bounds for the number of saddle connections and closed trajectories of a quadratic differential, Holomorphic functions and moduli, vol. 1, Springer-Verlag, 1988 | MR | Zbl
[Mi] On the number of factors of Sturmian words, Theor. Comp. Sci., Volume 82 (1991), pp. 71-84 | DOI | MR | Zbl
[MT] Rational billiards and flat structures (1999) (preprint Max Planck Institut) | MR | Zbl
[N] Orbit distribution on under the natural action of (2000) (IML preprint 21) | Zbl
[S] Introduction to ergodic theory, Princeton Univ. Press, 1976 | MR | Zbl
[T] Billiards, Panoramas et Synthèses, Soc. Math. France, 1995 | MR | Zbl
[Tr] Complexity lower bounds for polygonal billiards, Chaos, Volume 8 (1998), pp. 242-244 | DOI | MR | Zbl
[V] Teichmüller curves in moduli space, Eisenstein series and an application to triangular billiards, Invent. Math., Volume 97 (1989), pp. 553-583 | DOI | MR | Zbl
[V1] The billiard in a regular polygon, Geom. Func. Anal., Volume 2 (1992), pp. 341-379 | DOI | MR | Zbl
Cited by Sources: