On the structure of run-maximal strings

DOI10.1016/J.JDA.2011.08.005MaRDI QIDQ414413zbMATHOpenAlexFDO

Authors Antoine Deza, Frantisek Franek, Andrew Baker

Publication date 11 May 2012

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2011.08.005

zbMATH Keywords

stringrunsmaximum number of runs\(R\)-covercompression scheme

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Recommendations

• A computational framework for determining run-maximal strings
• The number of runs in a string
• The ``runs theorem
• On the maximal number of cubic runs in a string
• 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?)
• A characterization of the squares in a Fibonacci string
• A different proof of the Crochemore-Ilie lemma concerning microruns
• AN ASYMPTOTIC LOWER BOUND FOR THE MAXIMAL NUMBER OF RUNS IN A STRING
• Detecting leftmost maximal periodicities
• How many runs can a string contain?
• Maximal repetitions in strings
• Not So Many Runs in Strings
• Repetitive perhaps, but certainly not boring
• The Number of Runs in a String: Improved Analysis of the Linear Upper Bound
• The ``runs conjecture
• Towards a Solution to the “Runs” Conjecture

Cited in

(7)

• A \(d\)-step approach to the maximum number of distinct squares and runs in strings
• A computational framework for determining run-maximal strings
• A \(d\)-step approach for distinct squares in strings
• On the Maximal Sum of Exponents of Runsin a String
• On the maximal sum of exponents of runs in a string
• The Number of Runs in a String: Improved Analysis of the Linear Upper Bound
• A computational substantiation of the \(d\)-step approach to the number of distinct squares problem

This page was built for publication: On the structure of run-maximal strings

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