Kolmogorov complexity and non-determinism

DOI10.1016/S0304-3975(01)00038-XzbMath0982.68076MaRDI QIDQ5958289

Jean-Yves Marion, Serge Grigorieff

Publication date: 3 March 2002

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

zbMATH Keywords

Kolmogorov complexity

Mathematics Subject Classification ID

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

Cites Work

• Randomness conservation inequalities; information and independence in mathematical theories
• Kolmogorov and mathematical logic
• A Theory of Program Size Formally Identical to Information Theory
• Instance complexity
• Relations between varieties of kolmogorov complexities
• A variant of the Kolmogorov concept of complexity
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Kolmogorov complexity and non-determinism