The recurrence function $R(n)$ of an infinite word $u$ counts how long one has to wait to see every
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.

Date and Venue

Start Date
Venue
DMP-FCUP Sala 0.04

Speaker

Julien Cassaigne (Institut de mathematiques de Luminy, Marseille)

Area

Semigroups, Automata and Languages