The number of runs in Sturmian words

Abstract. Denote by S the class of standard Sturmian words. It is a class of highly compressible words extensively studied in combinatorics of words, includ-ing 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 w ∈ S, with respect to their recurrences (directive sequences). We show that ρ(w) |w| ≤ 4 5 for each w ∈ S, and there is an infinite sequence of strictly growing words wk ∈ S such that limk→ ∞ ρ(wk)|wk |