Complexity of Infinite Words

Complexity of infinite words is a widely studied field in combinatorics on words. A classical notion of a complexity of an infinite word is defined as a function counting, for each $n$, the number of its distinct factors (or blocks of consecutive letters) of length $n$. In their 1938 seminal paper on symbolic dynamics, Morse and Hedlund gave a relation between factor complexity and periodicity in infinite words; namely, they proved that each aperiodic infinite word $w$ has factor complexity at least $n+1$ for each length $n$. They further showed that an infinite word $w$ has factor complexity $n+1$ for each length $n$ if and only if $w$ is binary, aperiodic and balanced, i.e., $w$ is a Sturmian word. In the talk, we will consider various modifications of the notion of a complexity of infinite words and generalizations of Morse and Hedlund theorem.