Prague Stringology Conference 2011

Marcin Piątkowski and Wojciech Rytter

Computing the Number of Cubic Runs in Standard Sturmian Words

Abstract:
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.

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