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.
Mots-clés : curves, laminations on surfaces, symbolic dynamics, shifts, factor complexity, embedded graphs, train-tracks, Rauzy graphs, substitutions, spirals
@article{ITA_2014__48_4_391_0,
author = {Narbel, Philippe},
title = {Bouquets of circles for lamination languages and complexities},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {391--418},
publisher = {EDP-Sciences},
volume = {48},
number = {4},
year = {2014},
doi = {10.1051/ita/2014016},
mrnumber = {3302494},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ita/2014016/}
}
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 SP - 391 EP - 418 VL - 48 IS - 4 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ita/2014016/ DO - 10.1051/ita/2014016 LA - en ID - ITA_2014__48_4_391_0 ER -
%0 Journal Article %A Narbel, Philippe %T Bouquets of circles for lamination languages and complexities %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2014 %P 391-418 %V 48 %N 4 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ita/2014016/ %R 10.1051/ita/2014016 %G en %F ITA_2014__48_4_391_0
Narbel, Philippe. Bouquets of circles for lamination languages and complexities. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 48 (2014) no. 4, pp. 391-418. doi : 10.1051/ita/2014016. http://www.numdam.org/articles/10.1051/ita/2014016/
[1] , and , Topological entropy. Trans. Amer. Math. Soc. 114 (1965) 309-319. | MR | Zbl
[2] and , Automatic sequences. Cambridge University Press, Cambridge (2003). | MR | Zbl
[3] and , Représentation géométrique de suites de complexit*error*é2n + 1. Bull. Soc. Math. France 119 (1991) 199-215. | Numdam | MR | Zbl
[4] and , Words with low complexity and interval exchange transformations. Commun. Moscow Math. Soc. 63 (2008) 159-160. | Zbl
[5] , Geodesic laminations on surfaces. In Laminations and foliations in dynamics, geometry and topology, vol. 269 of Contemp. Math. Amer. Math. Soc. (2001) 1-37. | MR | Zbl
[6] , Foliations and the geometry of 3-manifolds. Oxford Mathematical Monographs. Oxford University Press, Oxford (2007). | MR | Zbl
[7] , Complexité et facteurs spéciaux. Bull. Belg. Math. Soc. 1 (1997) 67-88. | MR | Zbl
[8] and , Factor complexity, Combinatorics, automata and number theory, vol. 135 of Encyclopedia Math. Appl. Cambridge University Press, Cambridge (2010) 163-247. | MR | Zbl
[9] and , Automorphisms of surfaces after Nielsen and Thurston, vol. 9 of London Mathematical Society Student Texts. Cambridge University Press, Cambridge (1988). | MR | Zbl
[10] et al., A fixed-parameter approach to 2-layer planarization. Algorithmica 45 (2006) 159-182. | Zbl
[11] and Languages of k-interval exchange transformations. Bull. Lond. Math. Soc. 40 (2008) 705-714. | MR | Zbl
[12] , 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). | MR | Zbl
[13] , 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. | MR | Zbl
[14] and , Spiral Symmetry. World Scientific (1992). | MR
[15] , Measured lamination spaces for surfaces, from the topological viewpoint. Topology Appl. 30 (198) 8 63-88. | MR | Zbl
[16] , Interval exchange transformations. Math. Z. 141 (1975) 25-31. | MR | Zbl
[17] and , Symbolic Dynamics and Coding. Cambridge University Press, Cambridge (1995). | MR | Zbl
[18] and , Languages, D0L-systems, sets of curves, and surface automorphisms. Inform. Comput. 180 (2003) 30-52. | MR | Zbl
[19] and , Lamination languages. Ergodic Theory Dynam. Systems 33 (2013) 1813-1863. | MR | Zbl
[20] , Combinatorics on Words, number 17 in Encyclopedia of Math. Appl. Cambridge University Press, Cambridge (1997). | MR | Zbl
[21] , Ergodic Theory and Differentiable Dynamics. Springer-Verlag, Berlin (1987). | MR | Zbl
[22] and , Symbolic dynamics I. Amer. J. Math. 60 (1938) 815-866. | JFM | MR
[23] and , Symbolic dynamics II. Sturmian trajectories. Amer. J. Math. 62 (1940) 1-42. | JFM | MR
[24] , A construction of pseudo-Anosov homeomorphisms. Trans. Amer. Math. Soc. 310 (1988) 179-197. | MR | Zbl
[25] and , Combinatorics of train tracks, vol. 125 of Annal. Math. Studies. Princeton University Press, Princeton, NJ (1992). | MR | Zbl
[26] and , Infinite Words, number 141 in Pure Appl. Math. Elsevier (2004). | Zbl
[27] , Substitution dynamical systems-spectral analysis, 2nd Edition. Vol. 1294 of Lect. Notes Math. Springer-Verlag, Berlin (2010). | MR | Zbl
[28] , The geometry and topology of three-manifolds. Princeton University Lecture Notes (Electronic version 1.1, 2002). http://library.msri.org/books/gt3m (1980).
[29] , On the geometry and dynamics of diffeomorphisms of surfaces. Bull. Amer. Math. Soc. 19 (1988) 417-431. | MR | Zbl
Cité par Sources :
