Toward an abstract theory of data compression

DOI10.1016/0304-3975(83)90001-4zbMath0539.68032OpenAlexW2058958590MaRDI QIDQ794162

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 compressionGödel numberingrecursive functionundecidable problemabstract compression schemeabstract program size complexity

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Information-theoretic characterizations of recursive infinite strings
• Gödel numberings of partial recursive functions
• Computational complexity of formal translations
• A Theory of Program Size Formally Identical to Information Theory
• Optimal enumerations and optimal gödel numberings
• Noncomplex sequences: characterizations and examples
• On Simple Goedel Numberings and Translations
• A Machine-Independent Theory of the Complexity of Recursive Functions
• On the Length of Programs for Computing Finite Binary Sequences
• On the size of machines
• On the Length of Programs for Computing Finite Binary Sequences
• On the Simplicity and Speed of Programs for Computing Infinite Sets of Natural Numbers
• A variant of the Kolmogorov concept of complexity
• On Effective Procedures for Speeding Up Algorithms
• An Overview of the Theory of Computational Complexity

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