Bouquets of circles for lamination languages and complexities

Philippe Narbel

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2014)

  • Volume: 48, Issue: 4, page 391-418
  • ISSN: 0988-3754

Abstract

top
Laminations are classic sets of disjoint and non-self-crossing curves on surfaces. Lamination languages are languages of two-way infinite words which code laminations by using associated labeled embedded graphs, and which are subshifts. Here, we characterize the possible exact affine factor complexities of these languages through bouquets of circles, i.e. graphs made of one vertex, as representative coding graphs. We also show how to build families of laminations together with corresponding lamination languages covering all the possible exact affine complexities.

How to cite

top

Narbel, Philippe. "Bouquets of circles for lamination languages and complexities." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 48.4 (2014): 391-418. <http://eudml.org/doc/273049>.

@article{Narbel2014,
abstract = {Laminations are classic sets of disjoint and non-self-crossing curves on surfaces. Lamination languages are languages of two-way infinite words which code laminations by using associated labeled embedded graphs, and which are subshifts. Here, we characterize the possible exact affine factor complexities of these languages through bouquets of circles, i.e. graphs made of one vertex, as representative coding graphs. We also show how to build families of laminations together with corresponding lamination languages covering all the possible exact affine complexities.},
author = {Narbel, Philippe},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {curves; laminations on surfaces; symbolic dynamics; shifts; factor complexity; embedded graphs; train-tracks; Rauzy graphs; substitutions; spirals; pseudo-Anosov surface diffeomorphisms},
language = {eng},
number = {4},
pages = {391-418},
publisher = {EDP-Sciences},
title = {Bouquets of circles for lamination languages and complexities},
url = {http://eudml.org/doc/273049},
volume = {48},
year = {2014},
}

TY - JOUR
AU - Narbel, Philippe
TI - Bouquets of circles for lamination languages and complexities
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2014
PB - EDP-Sciences
VL - 48
IS - 4
SP - 391
EP - 418
AB - Laminations are classic sets of disjoint and non-self-crossing curves on surfaces. Lamination languages are languages of two-way infinite words which code laminations by using associated labeled embedded graphs, and which are subshifts. Here, we characterize the possible exact affine factor complexities of these languages through bouquets of circles, i.e. graphs made of one vertex, as representative coding graphs. We also show how to build families of laminations together with corresponding lamination languages covering all the possible exact affine complexities.
LA - eng
KW - curves; laminations on surfaces; symbolic dynamics; shifts; factor complexity; embedded graphs; train-tracks; Rauzy graphs; substitutions; spirals; pseudo-Anosov surface diffeomorphisms
UR - http://eudml.org/doc/273049
ER -

References

top
  1. [1] R.L. Adler, A.G. Konheim and M.H. McAndrew, Topological entropy. Trans. Amer. Math. Soc.114 (1965) 309–319. Zbl0127.13102MR175106
  2. [2] J-P. Allouche and J. Shallit, Automatic sequences. Cambridge University Press, Cambridge (2003). Zbl1086.11015MR1997038
  3. [3] P. Arnoux and G. Rauzy, Représentation géométrique de suites de complexit*error*é2n + 1. Bull. Soc. Math. France119 (1991) 199–215. Zbl0789.28011MR1116845
  4. [4] A. Ya. Belov and A.L. Chernyatiev, Words with low complexity and interval exchange transformations. Commun. Moscow Math. Soc.63 (2008) 159–160. Zbl1175.68307
  5. [5] F. Bonahon, Geodesic laminations on surfaces. In Laminations and foliations in dynamics, geometry and topology, vol. 269 of Contemp. Math. Amer. Math. Soc. (2001) 1–37. Zbl0996.53029MR1810534
  6. [6] D. Calegari, Foliations and the geometry of 3-manifolds. Oxford Mathematical Monographs. Oxford University Press, Oxford (2007). Zbl1118.57002MR2327361
  7. [7] J. Cassaigne, Complexité et facteurs spéciaux. Bull. Belg. Math. Soc.1 (1997) 67–88. Zbl0921.68065MR1440670
  8. [8] J. Cassaigne and F. Nicolas, Factor complexity, Combinatorics, automata and number theory, vol. 135 of Encyclopedia Math. Appl. Cambridge University Press, Cambridge (2010) 163–247. Zbl1216.68204MR2759107
  9. [9] A.J. Casson and S. Bleiler, Automorphisms of surfaces after Nielsen and Thurston, vol. 9 of London Mathematical Society Student Texts. Cambridge University Press, Cambridge (1988). Zbl0649.57008MR964685
  10. [10] V. Dujmović et al., A fixed-parameter approach to 2-layer planarization. Algorithmica45 (2006) 159–182. Zbl1095.68081
  11. [11] S. Ferenczi and L.Q. ZamboniLanguages of k-interval exchange transformations. Bull. Lond. Math. Soc.40 (2008) 705–714. Zbl1147.37008MR2441143
  12. [12] N. Pytheas Fogg, Substitutions in dynamics, arithmetics and combinatorics, vol. 1794 of Lect. Notes Math. Edited by V. Berthé, S. Ferenczi, C. Mauduit and A. Siegel. Springer, Verlag, Berlin (2002). Zbl1014.11015MR1970385
  13. [13] R.K. Guy, Outerthickness and outercoarseness of graphs, Combinatorics in Proc. British Combinatorial Conf., Univ. Coll. Wales, Aberystwyth, 1973. London Math. Soc. Lect. Note Ser. Cambridge University Press, London (1974) 57–60. Zbl0293.05108MR347652
  14. [14] I. Hargittai and C.A. Pickover, Spiral Symmetry. World Scientific (1992). MR1174143
  15. [15] A.E. Hatcher, Measured lamination spaces for surfaces, from the topological viewpoint. Topology Appl. 30 (198) 8 63–88. Zbl0662.57005MR964063
  16. [16] M. Keane, Interval exchange transformations. Math. Z.141 (1975) 25–31. Zbl0278.28010MR357739
  17. [17] D. Lind and B. Marcus, Symbolic Dynamics and Coding. Cambridge University Press, Cambridge (1995). Zbl1106.37301MR1369092
  18. [18] L.-M. Lopez and Ph. Narbel, Languages, D0L-systems, sets of curves, and surface automorphisms. Inform. Comput. 180 (2003) 30–52. Zbl1052.68078MR1951044
  19. [19] L.-M. Lopez and Ph. Narbel, Lamination languages. Ergodic Theory Dynam. Systems33 (2013) 1813–1863. Zbl1280.05068MR3122153
  20. [20] M. Lothaire, Combinatorics on Words, number 17 in Encyclopedia of Math. Appl. Cambridge University Press, Cambridge (1997). Zbl0874.20040MR1475463
  21. [21] R. Mañé, Ergodic Theory and Differentiable Dynamics. Springer-Verlag, Berlin (1987). Zbl0616.28007MR889254
  22. [22] M. Morse and G.A. Hedlund, Symbolic dynamics I. Amer. J. Math.60 (1938) 815–866. Zbl0019.33502MR1507944JFM64.0798.04
  23. [23] M. Morse and G.A. Hedlund, Symbolic dynamics II. Sturmian trajectories. Amer. J. Math. 62 (1940) 1–42. Zbl0022.34003MR745JFM66.0188.03
  24. [24] R.C. Penner, A construction of pseudo-Anosov homeomorphisms. Trans. Amer. Math. Soc.310 (1988) 179–197. Zbl0706.57008MR930079
  25. [25] R.C. Penner and J.L. Harer, Combinatorics of train tracks, vol. 125 of Annal. Math. Studies. Princeton University Press, Princeton, NJ (1992). Zbl0765.57001MR1144770
  26. [26] D. Perrin and J.P. Pin, Infinite Words, number 141 in Pure Appl. Math. Elsevier (2004). Zbl1094.68052
  27. [27] M. Quéffelec, Substitution dynamical systems-spectral analysis, 2nd Edition. Vol. 1294 of Lect. Notes Math. Springer-Verlag, Berlin (2010). Zbl1225.11001MR2590264
  28. [28] W.P. Thurston, The geometry and topology of three-manifolds. Princeton University Lecture Notes (Electronic version 1.1, 2002). http://library.msri.org/books/gt3m (1980). 
  29. [29] W.P. Thurston, On the geometry and dynamics of diffeomorphisms of surfaces. Bull. Amer. Math. Soc.19 (1988) 417–431. Zbl0674.57008MR956596

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.