AN ASYMPTOTIC LOWER BOUND FOR THE MAXIMAL NUMBER OF RUNS IN A STRING

DOI10.1142/S0129054108005620MaRDI QIDQ3532151zbMATH OpenOpenAlexFDO

Authors Frantisek Franek, Qian Yang

Publication date 3 November 2008

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054108005620

zbMATH Keywords

binary strings

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Recommendations

• Not So Many Runs in Strings
• A Series of Run-Rich Strings
• The number of runs in a string
• The Number of Runs in a String: Improved Analysis of the Linear Upper Bound
• Asymptotic behavior of the numbers of runs and microruns

Cites work

• Detecting leftmost maximal periodicities

Cited in

(21)

• On the Maximal Sum of Exponents of Runsin a String
• On the maximal sum of exponents of runs in a string
• scientific article; zbMATH DE number 7651171 (Why is no real title available?)
• The Number of Runs in a String: Improved Analysis of the Linear Upper Bound
• How many runs can a string contain?
• The maximal number of cubic runs in a word
• scientific article; zbMATH DE number 1431669 (Why is no real title available?)
• 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
• Repetitions in strings: algorithms and combinatorics
• On primary and secondary repetitions in words
• Computing primitively-rooted squares and runs in partial words
• Not So Many Runs in Strings
• A Series of Run-Rich Strings
• Computing the number of cubic runs in standard Sturmian words
• The ``runs theorem
• Three overlapping squares: the general case characterized \& applications
• Bannai et al. method proves the \(d\)-step conjecture for strings
• The number of q-ary words with restrictions on the length of the maximal run

This page was built for publication: AN ASYMPTOTIC LOWER BOUND FOR THE MAXIMAL NUMBER OF RUNS IN A STRING

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