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

periodicitystringrepetitionrun

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

• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• scientific article; zbMATH DE number 1390079 (Why is no real title available?)
• 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
• Intersecting periodic words
• Maximal repetitions in strings
• The Number of Runs in a String: Improved Analysis of the Linear Upper Bound
• The number of runs in a string
• Uniqueness Theorems for Periodic Functions

Cited in

(41)

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

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)