How many runs can a string contain?

DOI10.1016/J.TCS.2008.04.020MaRDI QIDQ935160zbMATH OpenOpenAlexFDO

Authors Simon J. Puglisi, W. F. Smyth, Jamie Simpson

Publication date 31 July 2008

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL http://researchrepository.murdoch.edu.au/id/eprint/27960/

zbMATH Keywords

periodicityrepetitionrunstring

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Recommendations

• The number of runs in a string
• A New Periodicity Lemma
• The Number of Runs in a String: Improved Analysis of the Linear Upper Bound
• Combinatorial Pattern Matching
• Maximal repetitions in strings

Cites work

• A New Periodicity Lemma
• AN ASYMPTOTIC LOWER BOUND FOR THE MAXIMAL NUMBER OF RUNS IN A STRING
• An optimal algorithm for computing the repetitions in a word
• Detecting leftmost maximal periodicities
• Fine and Wilf's theorem for three periods and a generalization of Sturmian words
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• scientific article; zbMATH DE number 1390079 (Why is no real title available?)
• Intersecting periodic words
• Maximal repetitions in strings
• The number of runs in a string
• The Number of Runs in a String: Improved Analysis of the Linear Upper Bound
• Uniqueness Theorems for Periodic Functions

Cited in

(43)

• Repetitions in strings: algorithms and combinatorics
• Asymptotic behavior of the numbers of runs and microruns
• How many squares can a string contain?
• The runs theorem and beyond
• Computing primitively-rooted squares and runs in partial words
• 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
• Lower bounds for the number of repetitions in 2D strings
• Optimal bounds for computing \({\alpha}\)-gapped repeats
• Some results on the number of periodic factors in words
• Three overlapping squares: the general case characterized \& applications
• Prefix frequency of lost positions
• The number of runs in a string
• On the average number of regularities in a word
• Is the string field big enough?
• On the Maximal Sum of Exponents of Runsin a String
• Fast and Practical Algorithms for Computing All the Runs in a String
• Towards a Solution to the “Runs” Conjecture
• Analysis of Maximal Repetitions in Strings
• Bounds on Powers in Strings
• Not So Many Runs in Strings
• On the maximal number of cubic runs in a string
• A Series of Run-Rich Strings
• Average value of sum of exponents of runs in a string
• The total run length of a word
• On the structure of run-maximal strings
• The three squares lemma revisited
• On the maximal sum of exponents of runs in a string
• Locating all maximal approximate runs in a string
• scientific article; zbMATH DE number 1390079 (Why is no real title available?)
• On the density of Lyndon roots in factors
• Bannai et al. method proves the \(d\)-step conjecture for strings
• The ``runs theorem
• The ``runs conjecture
• Combinatorial Pattern Matching
• A New Periodicity Lemma
• The number of repetitions in 2D-strings
• Optimal bounds for distinct quartics
• Linear time runs over general ordered alphabets
• On primary and secondary repetitions in words
• Efficiently computing runs on a trie
• Maximal repetitions in strings

This page was built for publication: How many runs can a string contain?

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