The maximal number of runs in standard Sturmian words (Q1953392)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The maximal number of runs in standard Sturmian words |
scientific article |
Statements
The maximal number of runs in standard Sturmian words (English)
0 references
7 June 2013
0 references
Summary: 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|\leq 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.
0 references
combinatorics on words
0 references
repetitions
0 references
compression
0 references