Polylog Space Compression Is Incomparable with Lempel-Ziv and Pushdown Compression

DOI10.1007/978-3-540-95891-8_56MaRDI QIDQ3599110zbMATH OpenOpenAlexFDO

Authors Elvira Mayordomo, Philippe Moser

Publication date 3 February 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-95891-8_56

zbMATH Keywords

compression algorithmscomputational complexitydata stream algorithmsLempel-Ziv algorithmplogonpushdown compression

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Analysis of algorithms and problem complexity (68Q25) Online algorithms; streaming algorithms (68W27)

Recommendations

• Polylog space compression, pushdown compression, and Lempel-Ziv are incomparable
• Pushdown compression
• A worst-case analysis of the LZ2 compression algorithm
• On optimal language compression for sets in PSPACE/poly
• On two LZ78-style grammars: compression bounds and compressed-space computation

Cites work

• Adding Nesting Structure to Words
• Bounded pushdown dimension vs Lempel Ziv information density
• Compression of individual sequences via variable-rate coding
• Finite-state dimension
• scientific article; zbMATH DE number 5269064 (Why is no real title available?)
• Mathematical Foundations of Computer Science 2005
• Note on normal numbers
• Optimal approximations of the frequency moments of data streams
• Pushdown compression
• The Construction of Decimals Normal in the Scale of Ten
• The space complexity of approximating the frequency moments

Cited in

(3)

• Bounded pushdown dimension vs Lempel Ziv information density
• Pushdown compression
• Polylog space compression, pushdown compression, and Lempel-Ziv are incomparable

This page was built for publication: Polylog Space Compression Is Incomparable with Lempel-Ziv and Pushdown Compression

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