We investigate some repetition problems for a very special class $\mathcal{S}$ of strings called the standard Sturmian words, which have very compact representations in terms of sequences of integers. Usually the size of this word is exponential with respect to the size of its integer sequence, hence we are dealing with repetition problems in compressed strings. An explicit formula is given for the number $\rho(w)$ of runs in a standard word $w$. We show that $\rho(w)/|w|\le 4/5$ for each $w\in S$, and there is an infinite sequence of strictly growing words $w_k\in {\mathcal{S}}$ such that $\lim_{k\rightarrow \infty} \frac{\rho(w_k)}{|w_k|} = \frac{4}{5}$. Moreover, we show how to compute the number of runs in a standard Sturmian word in linear time with respect to the size of its compressed representation.
@article{10_37236_2473,
author = {Pawe{\l} Baturo and Marcin Pi\k{a}tkowski and Wojciech Rytter},
title = {The maximal number of runs in standard {Sturmian} words},
journal = {The electronic journal of combinatorics},
year = {2013},
volume = {20},
number = {1},
doi = {10.37236/2473},
zbl = {1266.68144},
url = {http://geodesic.mathdoc.fr/articles/10.37236/2473/}
}
TY - JOUR
AU - Paweł Baturo
AU - Marcin Piątkowski
AU - Wojciech Rytter
TI - The maximal number of runs in standard Sturmian words
JO - The electronic journal of combinatorics
PY - 2013
VL - 20
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/2473/
DO - 10.37236/2473
ID - 10_37236_2473
ER -
%0 Journal Article
%A Paweł Baturo
%A Marcin Piątkowski
%A Wojciech Rytter
%T The maximal number of runs in standard Sturmian words
%J The electronic journal of combinatorics
%D 2013
%V 20
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/2473/
%R 10.37236/2473
%F 10_37236_2473
Paweł Baturo; Marcin Piątkowski; Wojciech Rytter. The maximal number of runs in standard Sturmian words. The electronic journal of combinatorics, Tome 20 (2013) no. 1. doi: 10.37236/2473
