Bounded size dictionary compression: SC^k-completeness and NC algorithms.

DOI10.1016/S0890-5401(02)00013-5MaRDI QIDQ1401920zbMATH OpenFDO

Authors Sergio De Agostino, Riccardo Silvestri

Publication date 19 August 2003

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

Full work available at URL https://doi.org/10.1016/S0890-5401(02)00013-5

zbMATH Keywords

Data compressionDictionary algorithmsNC algorithmsParallel complexitySC\(^k\)-completeness

Mathematics Subject Classification ID

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

Recommendations

• BOUNDED SIZE DICTIONARY COMPRESSION: RELAXING THE LRU DELETION HEURISTIC
• Compressed Dictionaries: Space Measures, Data Sets, and Experiments
• Compression estimates for a class of dictionary based compressors
• Compressed data structures: Dictionaries and data-aware measures
• Optimal-Time Dictionary-Compressed Indexes
• scientific article; zbMATH DE number 4155862
• Entropy lower bounds for dictionary compression
• scientific article; zbMATH DE number 975330
• P-complete problems in data compression
• Disk compression of k-mer sets

Cites work

• A taxonomy of problems with fast parallel algorithms
• A universal algorithm for sequential data compression
• Complexity theory of parallel time and hardware
• Compression of individual sequences via variable-rate coding
• Efficient parallel algorithms to test square-freeness and factorize strings
• scientific article; zbMATH DE number 1142309 (Why is no real title available?)
• scientific article; zbMATH DE number 784042 (Why is no real title available?)
• Multilist layering: Complexity and applications
• On Relating Time and Space to Size and Depth
• On uniform circuit complexity
• P-complete problems in data compression
• Relations Among Complexity Measures
• Towards a complexity theory of synchronous parallel computation

Cited in

(9)

• P-complete problems in data compression
• Worst-case analysis of the iterated longest fragment algorithm
• Lempel-Ziv data compression on parallel and distributed systems
• BOUNDED SIZE DICTIONARY COMPRESSION: RELAXING THE LRU DELETION HEURISTIC
• On the Hardness of Finding Optimal Multiple Preset Dictionaries
• The greedy approach to dictionary-based static text compression on a distributed system
• 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: Bounded size dictionary compression: SC\(^{k}\)-completeness and NC algorithms.

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