Sequences of low complexity: Automatic and Sturmian sequences. (English) Zbl 0976.11014

Berthé, Valérie

Blanchard, F. (ed.) et al., Topics in symbolic dynamics and applications. Courses given at the CIMPA-UNESCO summer school on symbolic dynamics and applications, Temuco, Chile, January 6-24, 1997. Cambridge: Cambridge University Press. Lond. Math. Soc. Lect. Note Ser. 279, 1-34 (2000).

This survey/course summarizes arithmetic, combinatorial and measure-theoretic properties of two families of sequences over finite alphabets, namely automatic sequences and Sturmian (billiard) sequences. These sequences have a “small” block-complexity (more precisely the number of blocks of length \(n\) occurring in such a sequence is \(O(n)\)). We invite the reader to follow the author in her promenade where she quotes 74 papers. We only add page numbers to Reference [63], namely 4-01-4-27 (note that “Séminaire de Théorie des Nombres” should read “Séminaire de Théorie des Nombres de Bordeaux”), and year for Reference [73], namely either 1982 or 2000.
Finally the following references have appeared: [15] J. Anal. Math. 79, 1-31 (1999; Zbl 0996.37006), [26] Theor. Comput. Sci. 230, 97-116 (2000; Zbl 0947.68543), [38] Ergodic Theory Dyn. Syst. 20, 1061-1078 (2000; Zbl 0965.37013), [43] Discrete Math. 206, 145-154 (1999; Zbl 0936.37008), [44] J. Number Theory 80, 1-24 (2000; Zbl 0974.11011).
For the entire collection see [Zbl 0942.00028].

Reviewer: Jean-Paul Allouche (Orsay)

MSC:

11B85	Automata sequences
37B10	Symbolic dynamics
11J81	Transcendence (general theory)
68R15	Combinatorics on words

Keywords:

Sturmian sequences; special factors; frequency of letters; transcendence in positive characteristic; rotations; survey; course; automatic sequences

Citations:

Zbl 0996.37006; Zbl 0947.68543; Zbl 0965.37013; Zbl 0936.37008; Zbl 0974.11011