Reconciling Data Compression and Kolmogorov Complexity

DOI10.1007/978-3-540-73420-8_56zbMath1171.68503OpenAlexW1485395638MaRDI QIDQ5428846

Wolfgang Merkle, Laurent Bienvenu

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

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

Related Items (9)

On stability of probability laws with respect to small violations of algorithmic randomness ⋮ Reducibilities relating to Schnorr randomness ⋮ Randomness, Computation and Mathematics ⋮ Sub-computable Bounded Pseudorandomness ⋮ Initial segment complexities of randomness notions ⋮ Coherence of reducibilities with randomness notions ⋮ ON A METRIC GENERALIZATION OF THE tt-DEGREES AND EFFECTIVE DIMENSION THEORY ⋮ Kolmogorov Complexity in Perspective Part I: Information Theory and Randomness ⋮ Schnorr triviality and its equivalent notions

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