We give a geometric representation of uniformly recurrent two-dimensional sequences of rectangular complexity function . We show that these sequences code a -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 . Nous montrons que ces suites codent l’action d’une -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}, pages = {179--208}, publisher = {Universit\'e Bordeaux I}, volume = {12}, number = {1}, year = {2000}, mrnumber = {1827847}, zbl = {1018.37010}, language = {fr}, url = {http://archive.numdam.org/item/JTNB_2000__12_1_179_0/} }
TY - JOUR AU - Berthé, Valérie AU - Vuillon, Laurent 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 - http://archive.numdam.org/item/JTNB_2000__12_1_179_0/ LA - fr ID - JTNB_2000__12_1_179_0 ER -
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://archive.numdam.org/item/JTNB_2000__12_1_179_0/
[1] Codages de rotations et basses complexités. Université Aix-Marseille II, Thèse, 1996.
,[2] Three distance theorems and combinatorics on words. Enseig. Math. 44 (1998), 103-132. | MR | Zbl
, ,[3] Sur la complexité des suites infinies. Bull. Belg. Math. Soc. 1 (1994), 133-143. | MR | Zbl
,[4] A two-dimensional generalization of Sturmian sequences: tilings and rotations. Prétirage 97-19, IML (Marseille).
, ,[5] Recent results in Sturmian words. Developments in Language Theory II (Dassow, Rozenberg, Salomaa eds) World Scientific 1996, pages 13-24. | MR | Zbl
,[6] Double sequences with complexity mn+1. J. Auto. Lang. Comb. 4 (1999), 153-170. | MR | Zbl
,[7] Hedlund, Sequences with minimal block growth. Math. Systems Theory 7 (1973), 138-153. | MR | Zbl
[8] On a conjecture on bidimensional words, prépublication, 1999.
, , ,[9] Complexity of sequences and dynamical systems. Discrète Math. 206 (1999), 145-154. | MR | Zbl
[10] Algebraic Combinatorics on Words. Chapitre 2: Sturmian words, par J. Berstel et P. Séébold. | MR
,[11] On the number of factors of Sturmian words. Theoret. Comput. Sci. 82 (1991), 71-84. | MR | Zbl
,[12] Symbolic dynamics. Amer. J. Math. 60 (1938), 815-866. | JFM | MR | Zbl
, ,[13] Symbolic dynamics II: Sturmian trajectories. Amer. J. Math. 62 (1940), 1-42. | JFM | MR | Zbl
, ,[14] Andriamampianina, Nombre de facteurs d'une suite infinie. Prépublication, 1994.
[15] Low complexity functions and convez sets in Zk. Mathem. Zeitschrift, à paraître. | Zbl
, ,[16] The complexity of functions on lattices. Theoret. Comput Sci., à paraître. | Zbl
, ,[17] The rectangle complexity of functions on two-dimensional lattices. Theoret. Comput Sci., à paraître. | Zbl
, ,[18] Gaps and steps for the sequence nθ mod 1. Proc. Cambridge Philos. Soc. 63 (1967), 1115-1123. | Zbl
,[19] On the distribution mod 1 of the sequence nα. Ann. Univ. Sci. Budapest, Eötvös Sect. Math. 1 (1958), 127-134. | Zbl
,[20] Ü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] On successive settings of an arc on the circumference of a circle. Fundamenta Math. 46 (1958), 187-189. | MR | Zbl
,[22] Communication privée.
,[23] Combinatoire des motifs d'une suite sturmienne bidimensionnelle. Theoret. Comput. Sci. 209 (1998), 261-285. | MR | Zbl
,