Suites doubles de basse complexité

Valérie Berthé; Laurent Vuillon

Journal de théorie des nombres de Bordeaux (2000)

  • Volume: 12, Issue: 1, page 179-208
  • ISSN: 1246-7405

Abstract

top
We give a geometric representation of uniformly recurrent two-dimensional sequences of rectangular complexity function m n + 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.

How to cite

top

Berthé, Valérie, and Vuillon, Laurent. "Suites doubles de basse complexité." Journal de théorie des nombres de Bordeaux 12.1 (2000): 179-208. <http://eudml.org/doc/248507>.

@article{Berthé2000,
abstract = {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 $\mathbb \{Z\}^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.},
author = {Berthé, Valérie, Vuillon, Laurent},
journal = {Journal de théorie des nombres de Bordeaux},
keywords = {two-dimensional sequences; low block-complexity; Sturmian sequences; irrational rotations},
language = {fre},
number = {1},
pages = {179-208},
publisher = {Université Bordeaux I},
title = {Suites doubles de basse complexité},
url = {http://eudml.org/doc/248507},
volume = {12},
year = {2000},
}

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
PB - Université Bordeaux I
VL - 12
IS - 1
SP - 179
EP - 208
AB - 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 $\mathbb {Z}^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.
LA - fre
KW - two-dimensional sequences; low block-complexity; Sturmian sequences; irrational rotations
UR - http://eudml.org/doc/248507
ER -

References

top
  1. [1] P. Alessandri, Codages de rotations et basses complexités. Université Aix-Marseille II, Thèse, 1996. 
  2. [2] P. Alessandri, V. Berthé, Three distance theorems and combinatorics on words. Enseig. Math.44 (1998), 103-132. Zbl0997.11051MR1643286
  3. [3] J.-P. Allouche, Sur la complexité des suites infinies. Bull. Belg. Math. Soc.1 (1994), 133-143. Zbl0803.68094MR1318964
  4. [4] V. berthé, L. Vuillon, A two-dimensional generalization of Sturmian sequences: tilings and rotations. Prétirage97-19, IML (Marseille). Zbl0970.68124
  5. [5] J. Berstel, Recent results in Sturmian words. Developments in Language Theory II (Dassow, Rozenberg, Salomaa eds) World Scientific1996, pages 13-24. Zbl1096.68689MR1466181
  6. [6] J. Cassaigne, Double sequences with complexity mn+1. J. Auto. Lang. Comb.4 (1999), 153-170. Zbl0971.68123MR1719387
  7. [7] E M. Coven, G.A.Hedlund, Sequences with minimal block growth. Math. Systems Theory7 (1973), 138-153. Zbl0256.54028MR322838
  8. [8] C. Epifanio, P. Mignosi, M. Koskas, On a conjecture on bidimensional words, prépublication, 1999. Zbl1040.68076
  9. [9] S. FerencziComplexity of sequences and dynamical systems. Discrète Math.206 (1999), 145-154. Zbl0936.37008MR1665394
  10. [10] M. Lothaire, Algebraic Combinatorics on Words. Chapitre 2: Sturmian words, par J. Berstel et P. Séébold. Zbl1001.68093MR1905123
  11. [11] F. Mignosi, On the number of factors of Sturmian words. Theoret. Comput. Sci.82 (1991), 71-84. Zbl0728.68093MR1112109
  12. [12] M. Morse, G.A. Hedlund, Symbolic dynamics. Amer. J. Math.60 (1938), 815-866. Zbl0019.33502MR1507944JFM64.0798.04
  13. [13] M. Morse, G.A. Hedlund, Symbolic dynamics II: Sturmian trajectories. Amer. J. Math.62 (1940), 1-42. Zbl0022.34003MR745JFM66.0188.03
  14. [14] D. RazafyAndriamampianina, Nombre de facteurs d'une suite infinie. Prépublication, 1994. 
  15. [15] J.W. Sander, R. Tijdeman, Low complexity functions and convez sets in Zk. Mathem. Zeitschrift, à paraître. Zbl1022.37011
  16. [16] J.W. Sander, R. Tijdeman, The complexity of functions on lattices. Theoret. Comput Sci., à paraître. Zbl1005.68118
  17. [17] J.W. Sander, R. Tijdeman, The rectangle complexity of functions on two-dimensional lattices. Theoret. Comput Sci., à paraître. Zbl0989.68062
  18. [18] N.B. Slater, Gaps and steps for the sequence nθ mod 1. Proc. Cambridge Philos. Soc.63 (1967), 1115-1123. Zbl0178.04703
  19. [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. Zbl0094.02903
  20. [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. Zbl0094.02904
  21. [21] S. Swierczkowski, On successive settings of an arc on the circumference of a circle. Fundamenta Math.46 (1958), 187-189. Zbl0085.27203MR104651
  22. [22] R. Tijdeman, Communication privée. 
  23. [23] L. Vuillon, Combinatoire des motifs d'une suite sturmienne bidimensionnelle. Theoret. Comput. Sci.209 (1998), 261-285. Zbl0913.68206MR1647534

NotesEmbed ?

top

You must be logged in to post comments.