1 - SEQUENCES OF LOW COMPLEXITY: AUTOMATIC AND STURMIAN SEQUENCES

Summary

Valérne BERTHE

Institut de Mathématiques de Luminy

CNRS-UPR 9016

Case 907, 163 avenue de Luminy

F-13288 Marseille Cedex 9

France

The complexity function is a classical measure of disorder for sequences with values in a finite alphabet: this function counts the number of factors of given length. We introduce here two characteristic families of sequences of low complexity function: automatic sequences and Sturmian sequences. We discuss their topological and measure-theoretic properties, by introducing some classical tools in combinatorics on words and in the study of symbolic dynamical systems.

Introduction

The aim of this course is to introduce two characteristic families of sequences of low “complexity”: automatic sequences and Sturmian sequences (complexity is defined here as the combinatorial function which counts the number of factors of given length of a sequence over a finite alphabet). These sequences not only occur in many mathematical fields but also in various domains as theoretical computer science, biology, physics, crystallography…

We first define some classical tools in combinatorics on words and in the study of symbolic dynamical systems: the complexity function and frequencies of factors in connection with the notions of topological and measure-theoretic entropy (Sections 1.2 and 1.3), the graphs of words (Section 1.4), special and bispecial factors (Section 1.5). Then we study Sturmian sequences in Section 1.6: these sequences are defined as the sequences of minimal complexity among non-ultimately periodic sequences. This combinatorial definition has the particularity of being equivalent to the following simple geometrical representation: a Sturmian sequence codes the orbit of a point of the unit circle under a rotation by irrational angle α with respect to a partition of the unit circle into two intervals of lengths α and 1 – α. Sturmian sequences have thus remarkable combinatorial and arithmetical properties.