Upper semi-lattice of binary strings with the relation ``\(x\) is simple conditional to \(y\)

DOI10.1016/S0304-3975(01)00032-9zbMath0992.68085WikidataQ57349836 ScholiaQ57349836MaRDI QIDQ5958283

Nikolai K. Vereshchagin, Andrei Romashchenko, Andrej A. Muchnik, Alexei Chernov, Alexander Shen

Publication date: 3 March 2002

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

Kolmogorov complexitycommon informationconditional complexity

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Related Items

Stability of properties of Kolmogorov complexity under relativization, INFORMATION DISTANCE AND ITS APPLICATIONS, On a connection between information and group lattices, An operational characterization of mutual information in algorithmic information theory, Kolmogorov Complexity as a Language, Nonapproximability of the normalized information distance, Unnamed Item, Calibrating Randomness

Cites Work

• On common information
• Inequalities for Shannon entropy and Kolmogorov complexity
• Pairs of words with nonmaterializable mutual information
• On degrees of unsolvability
• Unnamed Item
• Unnamed Item