{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T23:12:27Z","timestamp":1648595547694},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"We investigate some repetition problems for a very special class $\\mathcal{S}$ of strings called the standard Sturmian words, which\u00a0 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\u00a0 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.<\/jats:p>","DOI":"10.37236\/2473","type":"journal-article","created":{"date-parts":[[2020,1,10]],"date-time":"2020-01-10T22:00:33Z","timestamp":1578693633000},"source":"Crossref","is-referenced-by-count":3,"title":["The Maximal Number of Runs in Standard Sturmian Words"],"prefix":"10.37236","volume":"20","author":[{"given":"Pawe\u0142","family":"Baturo","sequence":"first","affiliation":[]},{"given":"Marcin","family":"Pi\u0105tkowski","sequence":"additional","affiliation":[]},{"given":"Wojciech","family":"Rytter","sequence":"additional","affiliation":[]}],"member":"23455","published-online":{"date-parts":[[2013,1,21]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v20i1p13\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v20i1p13\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,17]],"date-time":"2020-01-17T17:20:18Z","timestamp":1579281618000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v20i1p13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1,21]]},"references-count":0,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2013,1,7]]}},"URL":"http:\/\/dx.doi.org\/10.37236\/2473","relation":{},"ISSN":["1077-8926"],"issn-type":[{"value":"1077-8926","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1,21]]}}}