Kolmogorov complexity as a language
From MaRDI portal
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.
Recommendations
Cites work
- A criterion for extractability of mutual information for a triple of strings
- A strange application of Kolmogorov complexity
- An introduction to Kolmogorov complexity and its applications
- Combinatorial interpretation of Kolmogorov complexity
- Complex tilings
- Conditional complexity and codes
- Cryptographic security of individual instances
- Forbidden Substrings, Kolmogorov Complexity and Almost Periodic Sequences
- Hilbert's thirteenth problem and circuit complexity
- scientific article; zbMATH DE number 3427210 (Why is no real title available?)
- scientific article; zbMATH DE number 3497786 (Why is no real title available?)
- scientific article; zbMATH DE number 3291134 (Why is no real title available?)
- Inequalities for Shannon entropy and Kolmogorov complexity
- On a relation between information inequalities and group theory
- Partitioning multi-dimensional sets in a small number of ``uniform parts
- Randomness and recursive enumerability
- Recursively enumerable reals and Chaitin \(\Omega\) numbers
- Sets of K-independent strings
- The surprise examination paradox and the second incompleteness theorem
- Upper semi-lattice of binary strings with the relation ``\(x\) is simple conditional to \(y\)
Cited in
(11)- On the information carried by programs about the objects they compute
- Generalised entropies and asymptotic complexities of languages
- Around Kolmogorov complexity: basic notions and results
- scientific article; zbMATH DE number 4117885 (Why is no real title available?)
- scientific article; zbMATH DE number 1869614 (Why is no real title available?)
- A New Approach to Formal Language Theory by Kolmogorov Complexity
- Kolmogorov complexity of categories
- Generalised Entropy and Asymptotic Complexities of Languages
- scientific article; zbMATH DE number 4187790 (Why is no real title available?)
- Kolmogorov complexity as a combinatorial tool
- The application of the construction of Kolmogorov complexity and of a theorem by Maslov to semiotic systems
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)
