CSEDays. Theory 2014

Ural Federal University, Ekaterinburg, Russia, August 23 - August 25

News subscription


Для меня это была уже третья школа CSEDays. И, как я и ожидал, она оставила очень позитивные эмоции и дала очередной толчок к тому, чтобы сделать что-то грандиозное в мире Computer Science. Так что, лично я считаю, что школа удалась!
-- / CSEDays. Application 2011
Home / CSEDays. Theory 2014 / About the school / Lecturers /

Avoiding repetitions in words

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.