Prague Stringology Conference 2012

Marcin Piątkowski and Wojciech Rytter

The Number of Cubes in Sturmian Words

Abstract:
We design an efficient algorithm computing the number of distinct cubes in a standard Sturmian word given by its directive sequence (the special type of recurrences). The algorithm runs in linear time with respect to the size of the compressed representation (recurrences) describing the word, though the explicit size of the word can be exponential with respect to this representation. We give the explicit compact formula for the number of cubes in any standard word derived from the structural properties of runs (maximal repetitions). Fibonacci words are the most known subclass of standard Sturmian words. It is known that the ratio of the number of cubes to the size for Fibonacci words is asymptotically equal to
1
Φ3
≈ 0.2361
where Φ=
 5 +1
     2
. We show a class of standard Sturmian words for which this ratio is much higher and equals
3Φ+2
9Φ+4
≈ 0.36924841. An extensive experimentation suggests that this value is optimal.

Download article: Article in PostScript Article in PDF BibTeX Reference
 PostScript   PDF   BibTeX reference