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.
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00785244
Contributeur : Alexander Shen <>
Soumis le : mardi 5 février 2013 - 16:59:58
Dernière modification le : jeudi 24 mai 2018 - 15:59:23

Lien texte intégral

Identifiants

Collections

Citation

Bruno Bauwens, Alexander Shen. An Additivity Theorem for Plain Kolmogorov Complexity. Theory of Computing Systems, Springer Verlag, 2013, 52, pp.297-302. 〈http://link.springer.com/article/10.1007/s00224-012-9385-4〉. 〈10.1007/s00224-012-9385-4〉. 〈lirmm-00785244〉

Partager

Métriques

Consultations de la notice

122