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 compressionparallel computational complexityparallelization

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

• 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
• scientific article; zbMATH DE number 3919857 (Why is no real title available?)
• On the Complexity of Finite Sequences

Cited in

(12)

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

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)