Tight Upper Bounds on Distinct Maximal (Sub-)Repetitions in Highly Compressible Strings

DOI10.1142/S0129054122440075MaRDI QIDQ6169968zbMATH OpenOpenAlexFDO

Authors Julian Pape-Lange

Publication date 15 August 2023

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

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

zbMATH Keywords

combinatorics on wordshighly compressible stringsmaximal repetitionsmaximal subrepetitions

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Cites work

• A proof of Dejean’s conjecture
• A propos d'une conjecture de F. Dejean sur les répétitions dans les mots
• At the roots of dictionary compression: string attractors
• Dejean's conjecture and Sturmian words
• Dejean's conjecture holds for \(n\geq 30\)
• Dejean's conjecture holds for N ≥ 27
• Efficiently finding all maximal -gapped repeats
• Extracting powers and periods in a word from its runs structure
• Last cases of Dejean's conjecture
• On Dejean's conjecture over large alphabets
• On maximal repetitions of arbitrary exponent
• Optimal bounds for computing -gapped repeats
• Prefix frequency of lost positions
• Proof of Dejean's conjecture for alphabets with \(5, 6, 7, 8, 9, 10\) and \(11\) letters
• Sur un théorème de Thue
• The Number of Runs in a String: Improved Analysis of the Linear Upper Bound
• Two-dimensional maximal repetitions
• Uniformly growing k-th power-free homomorphisms
• Uniqueness Theorems for Periodic Functions
• Upper bounds on distinct maximal (sub-)repetitions in compressed strings

Cited in

(3)

• Tight bounds on the maximum number of shortest unique substrings
• Asymptotic Optimality of Antidictionary Codes
• Upper bounds on distinct maximal (sub-)repetitions in compressed strings

This page was built for publication: Tight Upper Bounds on Distinct Maximal (Sub-)Repetitions in Highly Compressible Strings

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