Kolmogorov Complexity as a Language
From MaRDI portal
Publication:3007621
DOI10.1007/978-3-642-20712-9_9zbMATH Open1330.68129DBLPconf/csr/Shen11arXiv1102.5418OpenAlexW1861788376WikidataQ57349556 ScholiaQ57349556MaRDI QIDQ3007621FDOQ3007621
Publication date: 17 June 2011
Published in: Computer Science – Theory and Applications (Search for Journal in Brave)
Abstract: The notion of Kolmogorov complexity (=the minimal length of a program that generates some object) is often useful as a kind of language that allows us to reformulate some notions and therefore provide new intuition. In this survey we provide (with minimal comments) many different examples where notions and statements that involve Kolmogorov complexity are compared with their counterparts not involving complexity.
Full work available at URL: https://arxiv.org/abs/1102.5418
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- An introduction to Kolmogorov complexity and its applications
- The Surprise Examination Paradox and the Second Incompleteness Theorem
- On a relation between information inequalities and group theory
- Complex tilings
- Inequalities for Shannon entropy and Kolmogorov complexity
- Forbidden Substrings, Kolmogorov Complexity and Almost Periodic Sequences
- Conditional complexity and codes
- Randomness and recursive enumerability
- Recursively enumerable reals and Chaitin \(\Omega\) numbers
- Cryptographic Security of Individual Instances
- Upper semi-lattice of binary strings with the relation ``\(x\) is simple conditional to \(y\)
- Combinatorial interpretation of Kolmogorov complexity
- Partitioning multi-dimensional sets in a small number of ``uniform parts
- A strange application of Kolmogorov complexity
- A criterion for extractability of mutual information for a triple of strings
- SETS OF K-INDEPENDENT STRINGS
- Hilbert’s Thirteenth Problem and Circuit Complexity
Cited In (3)
This page was built for publication: Kolmogorov Complexity as a Language
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3007621)
