|
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
where
Φ=.
We show a class of standard Sturmian words for which this ratio is much higher and equals ≈ 0.36924841.
An extensive experimentation suggests that this value is optimal.
|
