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)
68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)
94A15: Information theory (general)
Related Items
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