Upper bounds on distinct maximal (sub-)repetitions in compressed strings

DOI10.1007/978-3-030-81508-0_26OpenAlexW3190425932MaRDI QIDQ832954

Julian Pape-Lange

Publication date: 25 March 2022

Full work available at URL: https://doi.org/10.1007/978-3-030-81508-0_26

zbMATH Keywords

combinatorics on wordsmaximal repetitionscompressed stringsmaximal subrepetitions

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

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

Uses Software

• Combinatorics_Words

Cites Work

• Unnamed Item
• Extracting powers and periods in a word from its runs structure
• Maximal repetitions in strings
• On maximal repetitions of arbitrary exponent
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• Two-dimensional maximal repetitions
• Prefix frequency of lost positions
• Optimal Bounds for Computing $$\alpha $$ α -gapped Repeats
• The Smallest Grammar Problem
• Efficiently Finding All Maximal alpha-gapped Repeats
• Uniqueness Theorems for Periodic Functions
• The “Runs” Theorem
• The Number of Runs in a String: Improved Analysis of the Linear Upper Bound