Basic notions on substitutions

International audienceThe aim of this chapter is to introduce some concepts and to fix the notation we will use throughout this book. We will first introduce some terminology in combinatorics on words. These notions have their counterpart in terms of symbolic dynamics. We shall illustrate these definitions through the example of a particular sequence, the Morse sequence, generated by an algorithmic process we shall study in details in this book, namely a substitution. After recalling some basic notions on substitutions, we shall focus on the concept of automatic sequences. We then introduce the first notions of ergodic theory and focus on the spectral description of discrete dynamical systems