Combinatorics of Words

Introduction The basic object of this chapter is a word, that is a sequence -- finite or infinite -- of elements from a finite set. The very definition of a word immediately imposes two characteristic features on mathematical research of words, namely the discreteness and the noncommutativity. Therefore the combinatorial theory of words is a part of noncommutative discrete mathematics, which moreover often emphasizes the algorithmic nature of problems. It is worth recalling that in general noncommutative mathematical theories are much less developped than commutative ones. This explains, at least partly, why many simply formulated problems of words are very difficult to attack, or to put this more positively, mathematically challenging. The theory of words is profoundly connected to numerous different fields of mathematics and its applications. A natural environment of a word is a finitely generated free monoid, there