Suites doubles de basse complexité
Journal de théorie des nombres de Bordeaux, Volume 12 (2000) no. 1, p. 179-208
We give a geometric representation of uniformly recurrent two-dimensional sequences of rectangular complexity function mn+n. We show that these sequences code a 2 -action defined by two irrational rotations on the unit circle. The proof is based on a study of double sequences the lines of which are Sturmian sequences of same language.
Nous donnons une représentation géométrique des suites doubles uniformément récurrentes de fonction de complexité rectangulaire mn+n. Nous montrons que ces suites codent l’action d’une 2 -action définie par deux rotations irrationnelles sur le cercle unité. La preuve repose sur une étude des suites doubles dont les lignes sont des suite sturmiennes de même langage.
@article{JTNB_2000__12_1_179_0,
     author = {Berth\'e, Val\'erie and Vuillon, Laurent},
     title = {Suites doubles de basse complexit\'e},
     journal = {Journal de th\'eorie des nombres de Bordeaux},
     publisher = {Universit\'e Bordeaux I},
     volume = {12},
     number = {1},
     year = {2000},
     pages = {179-208},
     zbl = {1018.37010},
     mrnumber = {1827847},
     language = {fr},
     url = {http://www.numdam.org/item/JTNB_2000__12_1_179_0}
}
Berthé, Valérie; Vuillon, Laurent. Suites doubles de basse complexité. Journal de théorie des nombres de Bordeaux, Volume 12 (2000) no. 1, pp. 179-208. http://www.numdam.org/item/JTNB_2000__12_1_179_0/

[1] P. Alessandri, Codages de rotations et basses complexités. Université Aix-Marseille II, Thèse, 1996.

[2] P. Alessandri, V. Berthé, Three distance theorems and combinatorics on words. Enseig. Math. 44 (1998), 103-132. | MR 1643286 | Zbl 0997.11051

[3] J.-P. Allouche, Sur la complexité des suites infinies. Bull. Belg. Math. Soc. 1 (1994), 133-143. | MR 1318964 | Zbl 0803.68094

[4] V. Berthé, L. Vuillon, A two-dimensional generalization of Sturmian sequences: tilings and rotations. Prétirage 97-19, IML (Marseille).

[5] J. Berstel, Recent results in Sturmian words. Developments in Language Theory II (Dassow, Rozenberg, Salomaa eds) World Scientific 1996, pages 13-24. | MR 1466181 | Zbl 1096.68689

[6] J. Cassaigne, Double sequences with complexity mn+1. J. Auto. Lang. Comb. 4 (1999), 153-170. | MR 1719387 | Zbl 0971.68123

[7] E M. Coven, G.A. Hedlund, Sequences with minimal block growth. Math. Systems Theory 7 (1973), 138-153. | MR 322838 | Zbl 0256.54028

[8] C. Epifanio, P. Mignosi, M. Koskas, On a conjecture on bidimensional words, prépublication, 1999.

[9] S. Ferenczi Complexity of sequences and dynamical systems. Discrète Math. 206 (1999), 145-154. | MR 1665394 | Zbl 0936.37008

[10] M. Lothaire, Algebraic Combinatorics on Words. Chapitre 2: Sturmian words, par J. Berstel et P. Séébold. | MR 1905123

[11] F. Mignosi, On the number of factors of Sturmian words. Theoret. Comput. Sci. 82 (1991), 71-84. | MR 1112109 | Zbl 0728.68093

[12] M. Morse, G.A. Hedlund, Symbolic dynamics. Amer. J. Math. 60 (1938), 815-866. | JFM 64.0798.04 | MR 1507944 | Zbl 0019.33502

[13] M. Morse, G.A. Hedlund, Symbolic dynamics II: Sturmian trajectories. Amer. J. Math. 62 (1940), 1-42. | JFM 66.0188.03 | MR 745 | Zbl 0022.34003

[14] D. Razafy Andriamampianina, Nombre de facteurs d'une suite infinie. Prépublication, 1994.

[15] J.W. Sander, R. Tijdeman, Low complexity functions and convez sets in Zk. Mathem. Zeitschrift, à paraître. | Zbl 1022.37011

[16] J.W. Sander, R. Tijdeman, The complexity of functions on lattices. Theoret. Comput Sci., à paraître. | Zbl 1005.68118

[17] J.W. Sander, R. Tijdeman, The rectangle complexity of functions on two-dimensional lattices. Theoret. Comput Sci., à paraître. | Zbl 0989.68062

[18] N.B. Slater, Gaps and steps for the sequence nθ mod 1. Proc. Cambridge Philos. Soc. 63 (1967), 1115-1123. | Zbl 0178.04703

[19] V.T. Sós, On the distribution mod 1 of the sequence nα. Ann. Univ. Sci. Budapest, Eötvös Sect. Math. 1 (1958), 127-134. | Zbl 0094.02903

[20] J. Surányi, Über die Anordnung der Vielfachen einer reellen Zahl mod 1. Ann. Univ. Sci. Budapest, Eôtvôs Sect. Math. 1 (1958), 107-111. | Zbl 0094.02904

[21] S. Swierczkowski, On successive settings of an arc on the circumference of a circle. Fundamenta Math. 46 (1958), 187-189. | MR 104651 | Zbl 0085.27203

[22] R. Tijdeman, Communication privée.

[23] L. Vuillon, Combinatoire des motifs d'une suite sturmienne bidimensionnelle. Theoret. Comput. Sci. 209 (1998), 261-285. | MR 1647534 | Zbl 0913.68206