On the complexity and approximability of bounded access Lempel Ziv coding

DOI10.1007/978-3-031-66159-4_9MaRDI QIDQ7034838zbMATH OpenFDO

Authors Ferdinando Cicalese, Francesca Ugazio

Publication date 31 January 2025

Full work available at URL https://doi.org/10.1007/978-3-031-66159-4_9

zbMATH Keywords

approximationbounded access encodingLempel Ziv parsingNP-hardness

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites work

• 2726. A problem on strings of beads
• A theoretical and experimental analysis of BWT variants for string collections
• A universal algorithm for sequential data compression
• An upper bound and linear-space queries on the LZ-End parsing
• Complexity of approximating bounded variants of optimization problems
• Data compression via textual substitution
• Data structure lower bounds on random access to grammar-compressed strings
• Linear Algorithm for Data Compression via String Matching
• LZ-End Parsing in Linear Time
• On the approximation ratio of LZ-end to LZ77
• On the Complexity of Finite Sequences
• On the number of factors in the LZ-End factorization
• Optimal LZ-end parsing is hard
• Optimization, approximation, and complexity classes
• The Lempel–Ziv Complexity of Fixed Points of Morphisms

Cited in

(2)

• Hardness and approximability of bounded access Lempel Ziv coding
• Bat-LZ out of hell

This page was built for publication: On the complexity and approximability of bounded access Lempel Ziv coding

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