Stability of properties of Kolmogorov complexity under relativization
From MaRDI portal
Publication:619517
DOI10.1134/S0032946010010059zbMath1214.68182MaRDI QIDQ619517
Andrei Romashchenko, Andrej A. Muchnik
Publication date: 25 January 2011
Published in: Problems of Information Transmission (Search for Journal in Brave)
Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Information theory (general) (94A15)
Related Items (4)
Clustering with respect to the information distance ⋮ Algorithmic Statistics: Forty Years Later ⋮ An operational characterization of mutual information in algorithmic information theory ⋮ Algorithmic Statistics Revisited
Cites Work
- Unnamed Item
- On common information
- Inequalities for Shannon entropy and Kolmogorov complexity
- A new class of non-Shannon-type inequalities for entropies
- On characterization of entropy function via information inequalities
- Relations between varieties of kolmogorov complexities
- Appendix: On Common Information and Related Characteristics of Correlated Information Sources
- An introduction to Kolmogorov complexity and its applications
- Upper semi-lattice of binary strings with the relation ``\(x\) is simple conditional to \(y\)
- Conditional complexity and codes
- Combinatorial interpretation of Kolmogorov complexity
This page was built for publication: Stability of properties of Kolmogorov complexity under relativization
