Hostname: page-component-cd9895bd7-hc48f Total loading time: 0 Render date: 2024-12-28T00:50:18.182Z Has data issue: false hasContentIssue false
  • English
  • Français

Bouquets of circles for lamination languages and complexities

Published online by Cambridge University Press:  10 July 2014

Philippe Narbel
Philippe Narbel*
Affiliation:
LaBRI – UFR Math-Info, University of Bordeaux 1, 33405 Talence, France. . [email protected]
Get access

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.

Keywords

Curveslaminations on surfacessymbolic dynamicsshiftsfactor complexityembedded graphstrain-tracksRauzy graphssubstitutionsspirals
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 48 , Issue 4: Special issue in the honor of the 14th "Journées Montoises d'Informatique Théorique" , October 2014 , pp. 391 - 418
Copyright
© EDP Sciences 2014

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

Adler, R.L., Konheim, A.G. and McAndrew, M.H., Topological entropy. Trans. Amer. Math. Soc. 114 (1965) 309–319. Google Scholar
J-P. Allouche and J. Shallit, Automatic sequences. Cambridge University Press, Cambridge (2003).
Arnoux, P. and Rauzy, G., Représentation géométrique de suites de complexit*error*é2n + 1. Bull. Soc. Math. France 119 (1991) 199–215. Google Scholar
Belov, A. Ya. and Chernyatiev, A.L., Words with low complexity and interval exchange transformations. Commun. Moscow Math. Soc. 63 (2008) 159–160. Google Scholar
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.
D. Calegari, Foliations and the geometry of 3-manifolds. Oxford Mathematical Monographs. Oxford University Press, Oxford (2007).
Cassaigne, J., Complexité et facteurs spéciaux. Bull. Belg. Math. Soc. 1 (1997) 67–88. Google Scholar
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.
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).
Dujmović, V. et al., A fixed-parameter approach to 2-layer planarization. Algorithmica 45 (2006) 159–182. Google Scholar
Ferenczi, S. and Zamboni, L.Q. Languages of k-interval exchange transformations. Bull. Lond. Math. Soc. 40 (2008) 705–714. Google Scholar
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).
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.
I. Hargittai and C.A. Pickover, Spiral Symmetry. World Scientific (1992).
Hatcher, A.E., Measured lamination spaces for surfaces, from the topological viewpoint. Topology Appl. 30 (198) 8 63–88.
Keane, M., Interval exchange transformations. Math. Z. 141 (1975) 25–31. Google Scholar
D. Lind and B. Marcus, Symbolic Dynamics and Coding. Cambridge University Press, Cambridge (1995).
Lopez, L.-M. and Narbel, Ph., Languages, D0L-systems, sets of curves, and surface automorphisms. Inform. Comput. 180 (2003) 30–52. Google Scholar
Lopez, L.-M. and Narbel, Ph., Lamination languages. Ergodic Theory Dynam. Systems 33 (2013) 1813–1863. Google Scholar
M. Lothaire, Combinatorics on Words, number 17 in Encyclopedia of Math. Appl. Cambridge University Press, Cambridge (1997).
R. Mañé, Ergodic Theory and Differentiable Dynamics. Springer-Verlag, Berlin (1987).
Morse, M. and Hedlund, G.A., Symbolic dynamics I. Amer. J. Math. 60 (1938) 815–866. Google Scholar
Morse, M. and Hedlund, G.A., Symbolic dynamics II. Sturmian trajectories. Amer. J. Math. 62 (1940) 1–42. Google Scholar
Penner, R.C., A construction of pseudo-Anosov homeomorphisms. Trans. Amer. Math. Soc. 310 (1988) 179–197. Google Scholar
R.C. Penner and J.L. Harer, Combinatorics of train tracks, vol. 125 of Annal. Math. Studies. Princeton University Press, Princeton, NJ (1992).
D. Perrin and J.P. Pin, Infinite Words, number 141 in Pure Appl. Math. Elsevier (2004).
M. Quéffelec, Substitution dynamical systems-spectral analysis, 2nd Edition. Vol. 1294 of Lect. Notes Math. Springer-Verlag, Berlin (2010).
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).
Thurston, W.P., On the geometry and dynamics of diffeomorphisms of surfaces. Bull. Amer. Math. Soc. 19 (1988) 417–431. Google Scholar