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

DOI10.1007/s00224-010-9267-6zbMath1216.68105OpenAlexW2085603063WikidataQ60578963 ScholiaQ60578963MaRDI QIDQ538463

Sylvain Perifel, Philippe Moser, Elvira Mayordomo

Publication date: 25 May 2011

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-010-9267-6

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

Pushdown and Lempel-Ziv depth, Lightweight data indexing and compression in external memory, Bounded Pushdown Dimension vs Lempel Ziv Information Density, On the Difference Between Finite-State and Pushdown Depth

Cites Work

• Unnamed Item
• The space complexity of approximating the frequency moments
• Fractal dimension and logarithmic loss unpredictability.
• Finite-state dimension
• Bounded Pushdown Dimension vs Lempel Ziv Information Density
• Optimal approximations of the frequency moments of data streams
• Polylog Space Compression Is Incomparable with Lempel-Ziv and Pushdown Compression
• 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
• A note on preservation of languages by transducers
• Preservation of languages by transducers
• Note on normal numbers