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

DOI10.1007/S00224-010-9267-6zbMATH Open1216.68105DBLPjournals/mst/MayordomoMP11OpenAlexW2085603063WikidataQ60578963 ScholiaQ60578963MaRDI QIDQ538463FDOQ538463

Authors: Elvira Mayordomo, Philippe Moser, Sylvain Perifel 

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

Recommendations

• Pushdown compression
• Polylog Space Compression Is Incomparable with Lempel-Ziv and Pushdown Compression
• On two LZ78-style grammars: compression bounds and compressed-space computation
• Implementation and Application of Automata
• On the bit-complexity of Lempel-Ziv compression

zbMATH Keywords

computational complexityLempel-Ziv algorithmcompression algorithmsdata stream algorithmsplogonpushdown compression

Mathematics Subject Classification ID

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

Cites Work

• The space complexity of approximating the frequency moments
• Finite-state dimension
• Optimal approximations of the frequency moments of data streams
• Compression of individual sequences via variable-rate coding
• Note on normal numbers
• The Construction of Decimals Normal in the Scale of Ten
• Fractal dimension and logarithmic loss unpredictability.
• Bounded Pushdown Dimension vs Lempel Ziv Information Density
• Polylog Space Compression Is Incomparable with Lempel-Ziv and Pushdown Compression
• Adding Nesting Structure to Words
• Pushdown compression
• Title not available (Why is that?)
• Mathematical Foundations of Computer Science 2005
• A note on preservation of languages by transducers
• Preservation of languages by transducers

Cited In (7)

• Pebble-depth
• Pushdown and Lempel-Ziv depth
• Pushdown compression
• 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
• Polylog Space Compression Is Incomparable with Lempel-Ziv and Pushdown Compression

This page was built for publication: Polylog space compression, pushdown compression, and Lempel-Ziv are incomparable

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