P-complete problems in data compression

DOI10.1016/0304-3975(94)90106-6zbMath0805.68058OpenAlexW2071779672MaRDI QIDQ1325842

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

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

Related Items (8)

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

Cites Work

• Unnamed Item
• Efficient parallel algorithms to test square-freeness and factorize strings
• Data compression via textual substitution
• On the Complexity of Finite Sequences
• A universal algorithm for sequential data compression
• Compression of individual sequences via variable-rate coding

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