Bounded size dictionary compression: SC\(^{k}\)-completeness and NC algorithms.

DOI10.1016/S0890-5401(02)00013-5zbMath1054.68051MaRDI QIDQ1401920

Sergio De Agostino, Riccardo Silvestri

Publication date: 19 August 2003

Published in: Information and Computation (Search for Journal in Brave)

zbMATH Keywords

Data compressionNC algorithmsParallel complexityDictionary algorithmsSC\(^k\)-completeness

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Related Items (5)

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 ⋮ The greedy approach to dictionary-based static text compression on a distributed system ⋮ BOUNDED SIZE DICTIONARY COMPRESSION: RELAXING THE LRU DELETION HEURISTIC

Cites Work

• Unnamed Item
• Unnamed Item
• Multilist layering: Complexity and applications
• Complexity theory of parallel time and hardware
• On uniform circuit complexity
• Towards a complexity theory of synchronous parallel computation
• Efficient parallel algorithms to test square-freeness and factorize strings
• P-complete problems in data compression
• A taxonomy of problems with fast parallel algorithms
• On Relating Time and Space to Size and Depth
• A universal algorithm for sequential data compression
• Compression of individual sequences via variable-rate coding
• Relations Among Complexity Measures

This page was built for publication: Bounded size dictionary compression: SC\(^{k}\)-completeness and NC algorithms.