We give an introduction to the area of combinatorics on words, focusing on the theme of avoiding repetitions in words. The prototypical question in this area is: Does there exist an infinite sequence over 3 symbols such that no block ever repeats twice in succession? A positive answer was given by Thue in 1906. We will introduce the classical constructions for creating such sequences: namely, words created by iterating a morphism (morphic sequences) and words computed by a finite automaton (automatic sequences). We will discuss words avoiding more general patterns, such as fractional repetitions or abelian repetitions. Studying some of these generalizations involves the use of more advanced techniques. We will review some of these, including various non-constructive methods.
|Обязательно нужно сохранить традицию проведения "Что? Где? Когда?" или других интеллектуальных игр.|