Towards a Solution to the “Runs” Conjecture

DOI10.1007/978-3-540-69068-9_27zbMath1143.68510OpenAlexW1549299641MaRDI QIDQ3506961

Maxime Crochemore, Lucian Ilie, Liviu Tinta

Publication date: 17 June 2008

Published in: Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-69068-9_27

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Related Items (24)

ASYMPTOTIC BEHAVIOUR OF THE MAXIMAL NUMBER OF SQUARES IN STANDARD STURMIAN WORDS ⋮ Searching of gapped repeats and subrepetitions in a word ⋮ On the structure of run-maximal strings ⋮ The three squares lemma revisited ⋮ On the number of gapped repeats with arbitrary gap ⋮ On the average number of regularities in a word ⋮ On the maximal sum of exponents of runs in a string ⋮ On the Maximal Sum of Exponents of Runsin a String ⋮ Average number of occurrences of repetitions in a necklace ⋮ Computing the number of cubic runs in standard Sturmian words ⋮ 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 ⋮ On maximal repetitions of arbitrary exponent ⋮ Some results on the number of periodic factors in words ⋮ A Series of Run-Rich Strings ⋮ On the size of overlapping Lempel-Ziv and Lyndon factorizations ⋮ On primary and secondary repetitions in words ⋮ Repetitions in strings: algorithms and combinatorics ⋮ Asymptotic behavior of the numbers of runs and microruns ⋮ Three overlapping squares: the general case characterized \& applications

Cites Work

• How many runs can a string contain?
• Computing longest previous factor in linear time and applications
• Repetitions in strings: algorithms and combinatorics
• An optimal algorithm for computing the repetitions in a word
• Detecting leftmost maximal periodicities
• The number of runs in a string
• An O(n log n) algorithm for finding all repetitions in a string
• Analysis of Maximal Repetitions in Strings
• Not So Many Runs in Strings
• The Number of Runs in a String: Improved Analysis of the Linear Upper Bound

This page was built for publication: Towards a Solution to the “Runs” Conjecture