Suites doubles de basse complexité
Journal de théorie des nombres de Bordeaux, Volume 12 (2000) no. 1, pp. 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 = {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, Volume 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