×

zbMATH — the first resource for mathematics

Double sequences of low complexity. (Suites doubles de basse complexité.) (French) Zbl 1018.37010
M. Morse and G. A. Hedlund proved that a sequence containing at most \(n\) blocks of length \(n\) for some \(n\) must be periodic from some point on [Am. J. Math. 60, 815–866 (1938; Zbl 0019.33502)]. They also introduced Sturmian sequences [see ibid. 62, 1–42 (1940; Zbl 0022.34003)]: these are the sequences with exactly \(n+1\) blocks of length \(n\) for each \(n\geq 1\). The corresponding thresholds and the “right” notion of Sturmian sequences in dimension \(\geq 2\) are not really known yet. In the paper under review the authors study the 2D sequences that have \(mn+n\) rectangular blocks of size \((m,n)\) and that are uniformly recurrent. They show that these sequences code the \(\mathbb Z^2\)-action defined by two irrational rotations on \(\mathbb R/\mathbb Z\). Sturmian sequences occur in the proof. In passing the authors study the 2D sequences that contain \(m+n\) blocks of size \((m,n)\).
Please note that Reference [4] has appeared in Discrete Math. with a slightly modified title (see Zbl 0970.68124), that Reference [10] has appeared (see Zbl 1001.68093), that Reference [15] has appeared (see Zbl 1005.68118), and that Reference [17] has also appeared (see Zbl 0983.68062).

MSC:
37B10 Symbolic dynamics
11B83 Special sequences and polynomials
68R15 Combinatorics on words
PDF BibTeX XML Cite
Full Text: DOI Numdam EuDML
References:
[1] Alessandri, P., Codages de rotations et basses complexités. Université Aix-Marseille II, Thèse, 1996.
[2] Alessandri, P., Berthé, V., Three distance theorems and combinatorics on words. Enseig. Math.44 (1998), 103-132. · Zbl 0997.11051
[3] Allouche, J.-P., Sur la complexité des suites infinies. Bull. Belg. Math. Soc.1 (1994), 133-143. · Zbl 0803.68094
[4] berthé, V., Vuillon, L., A two-dimensional generalization of Sturmian sequences: tilings and rotations. Prétirage97-19, IML (Marseille). · Zbl 0970.68124
[5] Berstel, J., Recent results in Sturmian words. Developments in Language Theory II (Dassow, Rozenberg, Salomaa eds) World Scientific1996, pages 13-24. · Zbl 1096.68689
[6] Cassaigne, J., Double sequences with complexity mn+1. J. Auto. Lang. Comb.4 (1999), 153-170. · Zbl 0971.68123
[7] E, M.Coven, G.A.Hedlund, Sequences with minimal block growth. Math. Systems Theory7 (1973), 138-153. · Zbl 0256.54028
[8] Epifanio, C., Mignosi, P., Koskas, M., On a conjecture on bidimensional words, prépublication, 1999. · Zbl 1040.68076
[9] Ferenczi, S.Complexity of sequences and dynamical systems. Discrète Math.206 (1999), 145-154. · Zbl 0936.37008
[10] Lothaire, M., Algebraic Combinatorics on Words. Chapitre 2: Sturmian words, par J. Berstel et P. Séébold. · Zbl 1001.68093
[11] Mignosi, F., On the number of factors of Sturmian words. Theoret. Comput. Sci.82 (1991), 71-84. · Zbl 0728.68093
[12] Morse, M., Hedlund, G.A., Symbolic dynamics. Amer. J. Math.60 (1938), 815-866. · JFM 64.0798.04
[13] Morse, M., Hedlund, G.A., Symbolic dynamics II: Sturmian trajectories. Amer. J. Math.62 (1940), 1-42. · JFM 66.0188.03
[14] Razafy, D.Andriamampianina, Nombre de facteurs d’une suite infinie. Prépublication, 1994.
[15] Sander, J.W., Tijdeman, R., Low complexity functions and convez sets in Zk. Mathem. Zeitschrift, à paraître. · Zbl 1022.37011
[16] Sander, J.W., Tijdeman, R., The complexity of functions on lattices. Theoret. Comput Sci., à paraître. · Zbl 1005.68118
[17] Sander, J.W., Tijdeman, R., The rectangle complexity of functions on two-dimensional lattices. Theoret. Comput Sci., à paraître. · Zbl 0989.68062
[18] Slater, N.B., Gaps and steps for the sequence nθ mod 1. Proc. Cambridge Philos. Soc.63 (1967), 1115-1123. · Zbl 0178.04703
[19] Sós, V.T., 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] Surányi, J., Ü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] Swierczkowski, S., On successive settings of an arc on the circumference of a circle. Fundamenta Math.46 (1958), 187-189. · Zbl 0085.27203
[22] Tijdeman, R., Communication privée.
[23] Vuillon, L., Combinatoire des motifs d’une suite sturmienne bidimensionnelle. Theoret. Comput. Sci.209 (1998), 261-285. · Zbl 0913.68206
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.