Toward an abstract theory of data compression

DOI10.1016/0304-3975(83)90001-4MaRDI QIDQ794162zbMATH OpenOpenAlexFDO

Authors James A. Storer

Publication date 1983

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

Full work available at URL https://doi.org/10.1016/0304-3975(83)90001-4

zbMATH Keywords

computational complexitydata compressionrecursive functionundecidable problemabstract compression schemeabstract program size complexityGödel numbering

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Recursive functions and relations, subrecursive hierarchies (03D20)

Recommendations

• The macro model for data compression (extended abstract)
• scientific article; zbMATH DE number 78498
• A universal algorithm for sequential data compression
• Data compression
• A theory of incremental compression

Cites work

• scientific article; zbMATH DE number 3427210 (Why is no real title available?)
• scientific article; zbMATH DE number 3595170 (Why is no real title available?)
• scientific article; zbMATH DE number 3419039 (Why is no real title available?)
• A Machine-Independent Theory of the Complexity of Recursive Functions
• A Theory of Program Size Formally Identical to Information Theory
• A variant of the Kolmogorov concept of complexity
• An Overview of the Theory of Computational Complexity
• Computational complexity of formal translations
• Gödel numberings of partial recursive functions
• Information-theoretic characterizations of recursive infinite strings
• Noncomplex sequences: characterizations and examples
• On Effective Procedures for Speeding Up Algorithms
• On Simple Goedel Numberings and Translations
• On the Length of Programs for Computing Finite Binary Sequences
• On the Length of Programs for Computing Finite Binary Sequences
• On the Simplicity and Speed of Programs for Computing Infinite Sets of Natural Numbers
• On the size of machines
• Optimal enumerations and optimal gödel numberings

Cited in

(18)

• The macro model for data compression (extended abstract)
• Data compression using an ``imaginary sliding window
• Inequalities and algorithms for universal data compression
• About one formal schemes of information compression
• Distributed Compression through the Lens of Algorithmic Information Theory: A Primer
• scientific article; zbMATH DE number 3318548 (Why is no real title available?)
• A theory of incremental compression
• ?-Entropy data compression
• scientific article; zbMATH DE number 169463 (Why is no real title available?)
• Compression is Comprehension and the Unreasonable Effectiveness of Digital Computation in the Natural World
• Effective entropies and data compression
• Statistical mechanics of the data compression theorem
• scientific article; zbMATH DE number 1001409 (Why is no real title available?)
• Learning as Data Compression
• scientific article; zbMATH DE number 5806042 (Why is no real title available?)
• DAS KOMPRESSIONSTHEOREM FÜR TEMPOMASZE
• Redundancy of Lossless Data Compression for Known Sources by Analytic Methods
• Functional programs as compressed data

This page was built for publication: Toward an abstract theory of data compression

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