Reconciling Data Compression and Kolmogorov Complexity

DOI10.1007/978-3-540-73420-8_56MaRDI QIDQ5428846zbMATH OpenOpenAlexFDO

Authors Laurent Bienvenu, Wolfgang Merkle

Publication date 28 November 2007

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-73420-8_56

Mathematics Subject Classification ID

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

Recommendations

• On Kolmogorov complexity in the real Turing machine setting
• scientific article; zbMATH DE number 107774
• scientific article; zbMATH DE number 107775
• Kobayashi compressibility
• Automatic Kolmogorov complexity and normality revisited

Cited in

(17)

• Inequalities and algorithms for universal data compression
• An informational approach to the problem of compressing random processes
• Coherence of reducibilities with randomness notions
• Schnorr triviality and its equivalent notions
• Initial segment complexities of randomness notions
• On stability of probability laws with respect to small violations of algorithmic randomness
• Reducibilities relating to Schnorr randomness
• Randomness, computation and mathematics
• ?-Entropy data compression
• Sub-computable bounded pseudorandomness
• Compression and hadamard power inequalities
• Statistical mechanics of the data compression theorem
• Redundancy of Lossless Data Compression for Known Sources by Analytic Methods
• Compression is Comprehension and the Unreasonable Effectiveness of Digital Computation in the Natural World
• On a metric generalization of the \(tt\)-degrees and effective dimension theory
• Kolmogorov complexity in perspective. I: Information theory and randomness
• Epsilon Entropy and Data Compression

This page was built for publication: Reconciling Data Compression and Kolmogorov Complexity

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