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},
     doi = {10.5802/jtnb.274},
     zbl = {1018.37010},
     mrnumber = {1827847},
     language = {fr},
     url = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.274/}
}
TY  - JOUR
TI  - Suites doubles de basse complexité
JO  - Journal de Théorie des Nombres de Bordeaux
PY  - 2000
DA  - 2000///
SP  - 179
EP  - 208
VL  - 12
IS  - 1
PB  - Université Bordeaux I
UR  - https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.274/
UR  - https://zbmath.org/?q=an%3A1018.37010
UR  - https://www.ams.org/mathscinet-getitem?mr=1827847
UR  - https://doi.org/10.5802/jtnb.274
DO  - 10.5802/jtnb.274
LA  - fr
ID  - JTNB_2000__12_1_179_0
ER  - 
%0 Journal Article
%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://doi.org/10.5802/jtnb.274
%R 10.5802/jtnb.274
%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. 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

Cited by Sources: