The ``runs conjecture
From MaRDI portal
Publication:544875
DOI10.1016/j.tcs.2010.06.019zbMath1218.68113WikidataQ61677897 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
68Q25: Analysis of algorithms and problem complexity
68R15: Combinatorics on words
68W32: Algorithms on strings
Related Items
Computing the Antiperiod(s) of a String, The “Runs” Theorem, Unnamed Item, Finite and infinite closed-rich 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, 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, Counting maximal-exponent factors in words, Computing maximal-exponent factors in an overlap-free word, Computing primitively-rooted squares and runs in partial words, On \(k\)-abelian palindromes, On closed-rich words, Lower bounds for the number of repetitions in 2D strings, Three overlapping squares: the general case characterized \& applications, Prefix frequency of lost positions, On the average number of regularities in a word
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
