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.
@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},
volume = {48},
year = {2014},
pages = {391-418},
doi = {10.1051/ita/2014016},
mrnumber = {3302494},
language = {en},
url = {http://dml.mathdoc.fr/item/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) pp. 391-418. doi : 10.1051/ita/2014016. http://gdmltest.u-ga.fr/item/ITA_2014__48_4_391_0/
[1] , and , Topological entropy. Trans. Amer. Math. Soc. 114 (1965) 309-319. | MR 175106 | Zbl 0127.13102
[2] and , Automatic sequences. Cambridge University Press, Cambridge (2003). | MR 1997038 | Zbl 1086.11015
[3] and , Représentation géométrique de suites de complexit*error*é2n + 1. Bull. Soc. Math. France 119 (1991) 199-215. | Numdam | MR 1116845 | Zbl 0789.28011
[4] and , Words with low complexity and interval exchange transformations. Commun. Moscow Math. Soc. 63 (2008) 159-160. | Zbl 1175.68307
[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 1810534 | Zbl 0996.53029
[6] , Foliations and the geometry of 3-manifolds. Oxford Mathematical Monographs. Oxford University Press, Oxford (2007). | MR 2327361 | Zbl 1118.57002
[7] , Complexité et facteurs spéciaux. Bull. Belg. Math. Soc. 1 (1997) 67-88. | MR 1440670 | Zbl 0921.68065
[8] and , Factor complexity, Combinatorics, automata and number theory, vol. 135 of Encyclopedia Math. Appl. Cambridge University Press, Cambridge (2010) 163-247. | MR 2759107 | Zbl 1216.68204
[9] and , Automorphisms of surfaces after Nielsen and Thurston, vol. 9 of London Mathematical Society Student Texts. Cambridge University Press, Cambridge (1988). | MR 964685 | Zbl 0649.57008
[10] et al., A fixed-parameter approach to 2-layer planarization. Algorithmica 45 (2006) 159-182. | Zbl 1095.68081
[11] and Languages of k-interval exchange transformations. Bull. Lond. Math. Soc. 40 (2008) 705-714. | MR 2441143 | Zbl 1147.37008
[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 1970385 | Zbl 1014.11015
[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 347652 | Zbl 0293.05108
[14] and , Spiral Symmetry. World Scientific (1992). | MR 1174143
[15] , Measured lamination spaces for surfaces, from the topological viewpoint. Topology Appl. 30 (198) 8 63-88. | MR 964063 | Zbl 0662.57005
[16] , Interval exchange transformations. Math. Z. 141 (1975) 25-31. | MR 357739 | Zbl 0278.28010
[17] and , Symbolic Dynamics and Coding. Cambridge University Press, Cambridge (1995). | MR 1369092 | Zbl 1106.37301
[18] and , Languages, D0L-systems, sets of curves, and surface automorphisms. Inform. Comput. 180 (2003) 30-52. | MR 1951044 | Zbl 1052.68078
[19] and , Lamination languages. Ergodic Theory Dynam. Systems 33 (2013) 1813-1863. | MR 3122153 | Zbl 1280.05068
[20] , Combinatorics on Words, number 17 in Encyclopedia of Math. Appl. Cambridge University Press, Cambridge (1997). | MR 1475463 | Zbl 0874.20040
[21] , Ergodic Theory and Differentiable Dynamics. Springer-Verlag, Berlin (1987). | MR 889254 | Zbl 0616.28007
[22] and , Symbolic dynamics I. Amer. J. Math. 60 (1938) 815-866. | JFM 64.0798.04 | MR 1507944
[23] and , Symbolic dynamics II. Sturmian trajectories. Amer. J. Math. 62 (1940) 1-42. | JFM 66.0188.03 | MR 745
[24] , A construction of pseudo-Anosov homeomorphisms. Trans. Amer. Math. Soc. 310 (1988) 179-197. | MR 930079 | Zbl 0706.57008
[25] and , Combinatorics of train tracks, vol. 125 of Annal. Math. Studies. Princeton University Press, Princeton, NJ (1992). | MR 1144770 | Zbl 0765.57001
[26] and , Infinite Words, number 141 in Pure Appl. Math. Elsevier (2004). | Zbl 1094.68052
[27] , Substitution dynamical systems-spectral analysis, 2nd Edition. Vol. 1294 of Lect. Notes Math. Springer-Verlag, Berlin (2010). | MR 2590264 | Zbl 1225.11001
[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 956596 | Zbl 0674.57008