The ``runs conjecture
From MaRDI portal
Publication:544875
DOI10.1016/j.tcs.2010.06.019zbMath1218.68113OpenAlexW2011273749WikidataQ61677897 ScholiaQ61677897MaRDI QIDQ544875
Liviu Tinta, Lucian Ilie, Maxime Crochemore
Publication date: 16 June 2011
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2010.06.019
Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15) Algorithms on strings (68W32)
Related Items
Prefix frequency of lost positions, Lower bounds for the number of repetitions in 2D strings, Computing primitively-rooted squares and runs in partial words, Extracting powers and periods in a word from its runs structure, The total run length of a word, On palindromic factorization of words, Palindromes in circular words, On the structure of run-maximal strings, Finite and infinite closed-rich words, Computing maximal-exponent factors in an overlap-free word, The “Runs” Theorem, Unnamed Item, On the average number of regularities in a word, A \(d\)-step approach to the maximum number of distinct squares and runs in strings, Average number of occurrences of repetitions in a necklace, On the density of Lyndon roots in factors, On \(k\)-abelian palindromes, Counting maximal-exponent factors in words, Computing the Antiperiod(s) of a String, Three overlapping squares: the general case characterized \& applications, On closed-rich words
Cites Work
- Unnamed Item
- Maximal repetitions in strings
- How many runs can a string contain?
- Computing longest previous factor in linear time and applications
- Repetitions in strings: algorithms and combinatorics
- Transducers and repetitions
- Detecting leftmost maximal periodicities
- The number of runs in a string
- An O(n log n) algorithm for finding all repetitions in a string
- Towards a Solution to the “Runs” Conjecture
- Not So Many Runs in Strings
- The Number of Runs in a String: Improved Analysis of the Linear Upper Bound
