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

DOI10.1142/s0129054122440075OpenAlexW4309728841MaRDI QIDQ6169968

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 wordsmaximal repetitionsmaximal subrepetitionshighly compressible strings

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Cites Work

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