The ``runs conjecture

DOI10.1016/J.TCS.2010.06.019zbMATH Open1218.68113OpenAlexW2011273749WikidataQ61677897 ScholiaQ61677897MaRDI QIDQ544875FDOQ544875

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

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

zbMATH Keywords

compressionrunsrepetitionsalgorithms on strings

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (26)

• The total run length of a word
• On palindromic factorization of words
• Computing the Antiperiod(s) of a String
• Title not available (Why is that?)
• Palindromes in circular words
• 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)