Suites doubles de basse complexité
Journal de Théorie des Nombres de Bordeaux, Tome 12 (2000) no. 1, pp. 179-208.

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.

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.

@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},
     pages = {179--208},
     publisher = {Universit\'e Bordeaux I},
     volume = {12},
     number = {1},
     year = {2000},
     doi = {10.5802/jtnb.274},
     zbl = {1018.37010},
     mrnumber = {1827847},
     language = {fr},
     url = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.274/}
}
Valérie Berthé; Laurent Vuillon. Suites doubles de basse complexité. Journal de Théorie des Nombres de Bordeaux, Tome 12 (2000) no. 1, pp. 179-208. doi : 10.5802/jtnb.274. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.274/

[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