Skip to Main content Skip to Navigation
Journal articles

An Additivity Theorem for Plain Kolmogorov Complexity

Abstract : We prove the formula C(a, b) = K(a|C(a, b)) + C(b|a,C(a, b)) + O(1) that expresses the plain complexity of a pair in terms of prefix-free and plain conditional complexities of its components.
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00785244
Contributor : Alexander Shen <>
Submitted on : Tuesday, February 5, 2013 - 4:59:58 PM
Last modification on : Thursday, May 24, 2018 - 3:59:23 PM

Links full text

Identifiers

Collections

Citation

Bruno Bauwens, Alexander Shen. An Additivity Theorem for Plain Kolmogorov Complexity. Theory of Computing Systems, Springer Verlag, 2013, 52, pp.297-302. ⟨10.1007/s00224-012-9385-4⟩. ⟨lirmm-00785244⟩

Share

Metrics

Record views

197