![]()
1
Words and Sequences from Scratch
For the development of logical sciences it will be important, without consideration for possible applications, to find large domains for speculations about difficult problems. [...]
we present some investigations in the theory of sequences of symbols, a theory which has some connections with number theory.
Axel Thue [THU 12]
In this first chapter we introduce the basic objects that are encountered in the different parts of this book. The main aim is to give quick access (but without sacrificing a rigorous introduction) to some major notions arising in combinatorics on words. These are illustrated by many examples. The supporting goal is that, after reading this book, the reader should be able to fruitfully attend a research conference or seminar in the field. We do not present a proof of every stated result. We have made some choices depending on the notions and constructions that we want to emphasize.
Notions arising from automata theory are kept to a minimum (but we cannot avoid them completely when presenting words generated by constant-length morphisms). A self-contained presentation of finite automata and some of their properties is given in Chapter 1, Volume 2.
Here, we also present notions arising in (symbolic) dynamical systems, because the exchanges between these two areas of research should not be neglected and are profitable for both communities. Even though they are important, measure-theoretic notions and results coming from ergodic theory will not be presented in this book.
After this chapter, the reader will have been introduced to words, factor complexity, the formalism of symbolic dynamical systems, and Sturmian words. In the second chapter, we will present important classes of infinite words: k-automatic words and morphic words, with an emphasis on Perron–Frobenius theory. The chapters end with bibliographic notes giving pointers to further readings on the topics merely approached here. In the third chapter, we have put extra material on words: other measures of complexity of sequences, avoidance, recurrence and some tools, e.g. Rauzy graphs, to analyze words.
1.1. Mathematical background and notation
We start with some basic notation used throughout this book, and we finish this first section with a recap of some facts coming from algebraic number theory. We assume the reader to be familiar with usual basic set operations such as union, intersection or set difference: difference: ∪, ∩ or \. Sets of numbers are of particular interest. The set of non-negative integers (respectively integers, rational numbers, real numbers, complex numbers) is
(respectively
,
,
,
). Let
a be a real number and
= ,
,
,
or
. We set
For instance,
>0 can be written
\{0} or
≥1. Let
i,
j ∈
with
i ≤
j. We let
denote the set of integers {
i,
i + 1
, ..., j}
.We also assume the reader to be familiar with the most common algebraic structu...
