An Additivity Theorem for Plain Kolmogorov Complexity - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Journal Articles Theory of Computing Systems Year : 2013

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.

Domains

Information Theory [cs.IT] Information Theory [math.IT]

Alexander Shen  : Connect in order to contact the contributor

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00785244

Submitted on : Tuesday, February 5, 2013-4:59:58 PM

Last modification on : Tuesday, March 26, 2024-4:08:56 PM

Consult the full text

Dates and versions

lirmm-00785244 , version 1 (05-02-2013)

Identifiers

Cite

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

Export

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

CNRS ESCAPE LIRMM MIPS UNIV-MONTPELLIER
91 View
0 Download

Altmetric

Share

More