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 = {Val\'erie Berth\'e and Laurent Vuillon},
     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},
     zbl = {1018.37010},
     mrnumber = {1827847},
     language = {fr},
     url = {https://jtnb.centre-mersenne.org/item/JTNB_2000__12_1_179_0/}
}
TY  - JOUR
AU  - Valérie Berthé
AU  - Laurent Vuillon
TI  - Suites doubles de basse complexité
JO  - Journal de théorie des nombres de Bordeaux
PY  - 2000
SP  - 179
EP  - 208
VL  - 12
IS  - 1
PB  - Université Bordeaux I
UR  - https://jtnb.centre-mersenne.org/item/JTNB_2000__12_1_179_0/
LA  - fr
ID  - JTNB_2000__12_1_179_0
ER  - 
%0 Journal Article
%A Valérie Berthé
%A Laurent Vuillon
%T Suites doubles de basse complexité
%J Journal de théorie des nombres de Bordeaux
%D 2000
%P 179-208
%V 12
%N 1
%I Université Bordeaux I
%U https://jtnb.centre-mersenne.org/item/JTNB_2000__12_1_179_0/
%G fr
%F JTNB_2000__12_1_179_0
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. https://jtnb.centre-mersenne.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 | Zbl

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

[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 | Zbl

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

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

[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 | Zbl

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

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

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

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

[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

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

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

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

[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

[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

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

[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 | Zbl