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.
- Title
- An Additivity Theorem for Plain Kolmogorov Complexity
- Creators - without role
- Bruno Bauwens - Université de Montpellier, Laboratoire d'Informatique de Robotique et de Microélectronique de Mtp - LIRMMAlexander Shen - Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier
- Publication Details
- Theory of Computing Systems, Vol.52, pp.297-302
- Identifiers
- 9944970109311
- Academic Unit
- Laboratoire d'Informatique de Robotique et de Microélectronique de Mtp - LIRMM
- Language
- English
- Resource Type
- Journal article
- Local Fields
- lirmm-00785244