The standard Sturmian words
are extensively studied in combinatorics of words.
They are enough complicated to have many interesting properties and at the same time they are highly compressible.
In this paper we present compact formulas for the number ρ(3) of cubic runs in any standard word.
We show also that
| lim|w|→∞ | ρ(3)(w) |w| | = | (5Φ+3) (13Φ+9) | ≅ 0.36924841 |
and present the sequence of strictly growing standard words achieving this limit.
The exact asymptotic ratio is here irrational, contrary to the situation of squares and runs in the
same class of words.
Furthermore we design an
efficient algorithm computing the number of cubic runs in standard words
in linear time with respect to the
size of the compressed representation (recurrences) describing the word. The explicit size
of the word can be exponential with respect to this representation. This is yet another example of a very fast
computation on highly compressible
texts.
|
