Generalized straight-line programs

DOI10.1007/S00236-025-00481-3MaRDI QIDQ7018161zbMATH OpenFDO

Authors Gonzalo Navarro, Francisco Olivares, Cristian Urbina

Publication date 5 March 2025

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S00236-025-00481-3

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Grammars and rewriting systems (68Q42)

Cites work

• A separation between RLSLPs and LZ77
• A separation of \(\gamma\) and \(b\) via Thue-Morse words
• An upper bound and linear-space queries on the LZ-End parsing
• At the roots of dictionary compression: string attractors
• Balancing run-length straight-line programs
• Balancing Straight-line Programs
• Bit catastrophes for the Burrows-Wheeler transform
• Burrows-Wheeler transform and Sturmian words
• Collapsing the hierarchy of compressed data structures: suffix arrays in optimal compressed space
• Data compression via textual substitution
• Data structure lower bounds on random access to grammar-compressed strings
• Efficient randomized pattern-matching algorithms
• Faster entropy-bounded compressed suffix trees
• Fingerprints in compressed strings
• Fully functional suffix trees and optimal text searching in BWT-runs bounded space
• Grammar-compressed indexes with logarithmic search time
• scientific article; zbMATH DE number 1740032 (Why is no real title available?)
• Iterated straight-line programs
• L-systems for measuring repetitiveness
• Near-optimal search time in -optimal space, and vice versa
• Novel results on the number of runs of the Burrows-Wheeler-transform
• On compressing and indexing repetitive sequences
• On cube-free \(\omega\)-words generated by binary morphisms
• On stricter reachable repetitiveness measures
• On the Approximation Ratio of Ordered Parsings
• On the Complexity of Finite Sequences
• On the impact of morphisms on BWT-runs
• Optimal-Time Dictionary-Compressed Indexes
• Random access to grammar-compressed strings and trees
• Resolution of the Burrows-Wheeler transform conjecture
• Sensitivity of string compressors and repetitiveness measures
• Sorted range reporting
• Space-efficient preprocessing schemes for range minimum queries on static arrays
• Sublinear algorithms for approximating string compressibility
• The Smallest Grammar Problem
• Toward a Definitive Compressibility Measure for Repetitive Sequences

This page was built for publication: Generalized straight-line programs

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