Discrete Algebraic Methods

6 Combinatorics on words

Combinatorics on words deals with structural statements and properties of words and formal languages. Typical applications are text algorithms such as pattern recognition and the theory of variable length codes. The foundations were laid by the Norwegian mathematician Axel Thue (1863–1922) in the early 20th century. We refer to the Lothaire textbooks [66–68] for background information and highlights in this field.

Let Σ be a set. We view Σ as an alphabet and the elements of Σ are therefore called letters. We are mainly interested in the case where Σ is finite. By Σn, we denote the set of sequences of n letters over Σ. For (a1, . . . , an)∈ Σn, we also write a1 ⋅⋅ ⋅ an. We say that a1 ⋅⋅ ⋅ an is a word of length |a1