On a question of Morse and Hedlund on the recurrence function of infinite words

DMP-FCUP Sala 0.04
Wednesday, 22 February, 2006 - 17:00

The recurrence function $R(n)$ of an infinite word $u$ counts how long one has to wait to see every word of length $n$ that occurs in $u$. Morse and Hedlund studied the behaviour of this function for Sturmian words in 1940, and asked the following question: can $R(n)\over n$ have a finite limit, when $u$ is not periodic? We provide a negative answer to that question, based on a detailed study of bispecial factors. As a byproduct, we also answer a similar question of Heinis (2001) on the subword complexity function.

Speaker: 

Julien Cassaigne (Institut de mathématiques de Luminy, Marseille)