How many runs can a string contain?
From MaRDI portal
Publication:935160
DOI10.1016/j.tcs.2008.04.020zbMath1155.68070OpenAlexW1998674287MaRDI QIDQ935160
W. F. Smyth, Simon J. Puglisi, R. Jamie Simpson
Publication date: 31 July 2008
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: http://researchrepository.murdoch.edu.au/id/eprint/27960/
Related Items (29)
Prefix frequency of lost positions ⋮ Lower bounds for the number of repetitions in 2D strings ⋮ Computing primitively-rooted squares and runs in partial words ⋮ The total run length of a word ⋮ Towards a Solution to the “Runs” Conjecture ⋮ On the structure of run-maximal strings ⋮ The three squares lemma revisited ⋮ The “Runs” Theorem ⋮ Unnamed Item ⋮ On the average number of regularities in a word ⋮ On the maximal sum of exponents of runs in a string ⋮ Bounds on Powers in Strings ⋮ Not So Many Runs in Strings ⋮ Maximal repetitions in strings ⋮ On the Maximal Sum of Exponents of Runsin a String ⋮ On the density of Lyndon roots in factors ⋮ Bannai et al. method proves the \(d\)-step conjecture for strings ⋮ The maximal number of cubic runs in a word ⋮ Computing regularities in strings: a survey ⋮ On the maximum number of cubic subwords in a word ⋮ The ``runs conjecture ⋮ Optimal bounds for computing \({\alpha}\)-gapped repeats ⋮ Some results on the number of periodic factors in words ⋮ A Series of Run-Rich Strings ⋮ On primary and secondary repetitions in words ⋮ Repetitions in strings: algorithms and combinatorics ⋮ AVERAGE VALUE OF SUM OF EXPONENTS OF RUNS IN A STRING ⋮ Asymptotic behavior of the numbers of runs and microruns ⋮ Three overlapping squares: the general case characterized \& applications
Cites Work
- Unnamed Item
- Unnamed Item
- Maximal repetitions in strings
- Intersecting periodic words
- An optimal algorithm for computing the repetitions in a word
- Fine and Wilf's theorem for three periods and a generalization of Sturmian words
- Detecting leftmost maximal periodicities
- The number of runs in a string
- AN ASYMPTOTIC LOWER BOUND FOR THE MAXIMAL NUMBER OF RUNS IN A STRING
- Uniqueness Theorems for Periodic Functions
- The Number of Runs in a String: Improved Analysis of the Linear Upper Bound
- A New Periodicity Lemma
This page was built for publication: How many runs can a string contain?
