Toward an abstract theory of data compression
From MaRDI portal
Publication:794162
DOI10.1016/0304-3975(83)90001-4zbMath0539.68032OpenAlexW2058958590MaRDI QIDQ794162
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
computational complexitydata compressionGödel numberingrecursive functionundecidable problemabstract compression schemeabstract program size complexity
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
