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

DOI10.1007/S00224-010-9267-6MaRDI QIDQ538463zbMATH OpenOpenAlexDBLPWikidataFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 5269064 (Why is no real title available?)
• A note on preservation of languages by transducers
• Adding Nesting Structure to Words
• Bounded pushdown dimension vs Lempel Ziv information density
• Compression of individual sequences via variable-rate coding
• Finite-state dimension
• Fractal dimension and logarithmic loss unpredictability.
• Mathematical Foundations of Computer Science 2005
• Note on normal numbers
• Optimal approximations of the frequency moments of data streams
• Polylog Space Compression Is Incomparable with Lempel-Ziv and Pushdown Compression
• Preservation of languages by transducers
• Pushdown compression
• The Construction of Decimals Normal in the Scale of Ten
• The space complexity of approximating the frequency moments

Cited in

(7)

• Pebble-depth
• Pushdown and Lempel-Ziv depth
• On the difference between finite-state and pushdown depth
• Pushdown compression
• Bounded pushdown dimension vs Lempel Ziv information density
• Lightweight data indexing and compression in external memory
• 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)