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

DOI10.1007/978-3-540-95891-8_56zbMath1206.68113OpenAlexW1545039096MaRDI QIDQ3599110

Philippe Moser, Elvira Mayordomo

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

computational complexitycompression algorithmsLempel-Ziv algorithmdata stream algorithmsplogonpushdown compression

Mathematics Subject Classification ID

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

Related Items (1)

Polylog space compression, pushdown compression, and Lempel-Ziv are incomparable

Cites Work

• Unnamed Item
• The space complexity of approximating the frequency moments
• Finite-state dimension
• Bounded Pushdown Dimension vs Lempel Ziv Information Density
• Optimal approximations of the frequency moments of data streams
• Adding Nesting Structure to Words
• Compression of individual sequences via variable-rate coding
• The Construction of Decimals Normal in the Scale of Ten
• Pushdown Compression
• Mathematical Foundations of Computer Science 2005
• Note on normal numbers

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