Rob Tijdeman: Substitutions and multi-dimensional words

Sturmian sequences (or equivalently cutting sequences, Beatty sequences or regular sequences) are the best discrete approximations to straight lines in $\mathbb{R}^2$. They can be presented by substitutions, but also by continued fractions. For more information see e.g. Chapter 2 of [3]. Multi-dimensional Sturmian words are the best discrete approximations to hyperplanes in $\mathbb{R}^k$ for any $k>2$. The case $k=3$ was studied by Berthé and Vuillon [2]. In a joint paper with Berthé [1] and in a single author paper (to appear) the relation with substitutions and multi-dimensional continued fractions is worked out. A special case leads to the well known Rauzy fractal. The lecture will give a survey of the developed ideas and obtained results.

Bibliography

1

Valérie Berthé and Robert Tijdeman.
Lattices and multi-dimensional words.
Theoret. Comput. Sci., 319(1-3):177-202, 2004.

2

Valérie Berthé and Laurent Vuillon.
Tilings and rotations on the torus: a two-dimensional generalization of Sturmian sequences.
Discrete Math., 223(1-3):27-53, 2000.

3

M. Lothaire.
Algebraic combinatorics on words, volume 90 of Encyclopedia of Mathematics and its Applications.
Cambridge University Press, Cambridge, 2002.

Back to the Index