P-complete problems in data compression

DOI10.1016/0304-3975(94)90106-6MaRDI QIDQ1325842zbMATH OpenOpenAlexFDO

Authors Sergio De Agostino

Publication date 26 January 1995

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(94)90106-6

zbMATH Keywords

data compressionparallelizationparallel computational complexity

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Analysis of algorithms and problem complexity (68Q25) Distributed algorithms (68W15)

Recommendations

• Bounded size dictionary compression: SC\(^{k}\)-completeness and NC algorithms.
• Parallelism and dictionary based data compression
• Lempel-Ziv data compression on parallel and distributed systems
• scientific article; zbMATH DE number 784042
• Publication:4941888

Cites work

• scientific article; zbMATH DE number 3919857 (Why is no real title available?)
• A universal algorithm for sequential data compression
• Compression of individual sequences via variable-rate coding
• Data compression via textual substitution
• Efficient parallel algorithms to test square-freeness and factorize strings
• On the Complexity of Finite Sequences

Cited in

(12)

• Inequalities and algorithms for universal data compression
• On compressing complete designs
• Greedy versus optimal analysis of bounded size dictionary compression and on-the-fly distributed computing
• Concurrent vs. exclusive reading in parallel decoding of LZ-compressed files
• Lempel-Ziv data compression on parallel and distributed systems
• BOUNDED SIZE DICTIONARY COMPRESSION: RELAXING THE LRU DELETION HEURISTIC
• A PTIME-complete matching problem for SLP-compressed words
• A theory of strict P-completeness
• Compression and hadamard power inequalities
• Scalability and communication in parallel low-complexity lossless compression
• Parallelism and dictionary based data compression
• Bounded size dictionary compression: SC\(^{k}\)-completeness and NC algorithms.

This page was built for publication: P-complete problems in data compression

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