The Number of Runs in Sturmian Words

Denote by

the class of

standard Sturmian

words. It is a class of highly compressible words extensively studied in combinatorics of words, including the well known Fibonacci words. The suffix automata for these words have a very particular structure. This implies a simple characterization (described in the paper by the Structural Lemma) of the periods of runs (maximal repetitions) in Sturmian words. Using this characterization we derive an explicit formula for the number

ρ

(

w

) of runs in words

, with respect to their

recurrences

(

directive sequences

). We show that

$\frac{\rho(w)}{|w|}\le \frac{4}{5} \textrm{\ for each\ }\ w\in {\cal S},$

and there is an infinite sequence of strictly growing words

$w_k\in {\cal S}$

such that

$\lim_{k\rightarrow \infty}\ \frac{\rho(w_k)}{|w_k|}\ =\ \frac{4}{5}$

. The complete understanding of the function

ρ

for a large class

of complicated words is a step towards better understanding of the structure of runs in words. We also show how to compute the number of runs in a standard Sturmian word in linear time with respect to the size of its compressed representation (recurrences describing the word). This is an example of a very fast computation on texts given implicitly in terms of a special grammar-based compressed representation (usually of logarithmic size with respect to the explicit text).