The ``runs conjecture

DOI10.1016/J.TCS.2010.06.019MaRDI QIDQ544875zbMATH OpenOpenAlexWikidataFDO

Authors Lucian Ilie, Liviu Tinta, 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

zbMATH Keywords

compressionrunsrepetitionsalgorithms on strings

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15) Algorithms on strings (68W32)

Recommendations

• Towards a Solution to the “Runs” Conjecture
• The runs theorem and beyond
• The ``runs theorem
• How many runs can a string contain?
• The Number of Runs in a String: Improved Analysis of the Linear Upper Bound

Cites work

• scientific article; zbMATH DE number 5717191 (Why is no real title available?)
• An O(n log n) algorithm for finding all repetitions in a string
• Computing longest previous factor in linear time and applications
• Detecting leftmost maximal periodicities
• How many runs can a string contain?
• Maximal repetitions in strings
• Not So Many Runs in Strings
• Repetitions in strings: algorithms and combinatorics
• The Number of Runs in a String: Improved Analysis of the Linear Upper Bound
• The number of runs in a string
• Towards a Solution to the “Runs” Conjecture
• Transducers and repetitions

Cited in

(26)

• The total run length of a word
• On palindromic factorization of words
• Computing the Antiperiod(s) of a String
• Palindromes in circular words
• scientific article; zbMATH DE number 7651171 (Why is no real title available?)
• Finite and infinite closed-rich words
• On closed-rich words
• On k-abelian palindromes
• Extracting powers and periods in a word from its runs structure
• Counting maximal-exponent factors in words
• Prefix frequency of lost positions
• On the average number of regularities in a word
• Lower bounds for the number of repetitions in 2D strings
• On the structure of run-maximal strings
• A \(d\)-step approach to the maximum number of distinct squares and runs in strings
• The runs theorem and beyond
• Computing primitively-rooted squares and runs in partial words
• Average number of occurrences of repetitions in a necklace
• A different proof of the Crochemore-Ilie lemma concerning microruns
• The ``runs theorem
• Towards a Solution to the “Runs” Conjecture
• On the density of Lyndon roots in factors
• Running Clubs-A Combinatorial Investigation
• Three overlapping squares: the general case characterized \& applications
• Bannai et al. method proves the \(d\)-step conjecture for strings
• Computing maximal-exponent factors in an overlap-free word

This page was built for publication: The ``runs conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q544875)