An Additivity Theorem for Plain Kolmogorov Complexity

被引：0
|
作者：
Bruno Bauwens
Alexander Shen
机构：
[1] Instituto de Telecomunicações Faculdade de Ciência at Porto University,Laboratoire d’Informatique, de Robotique et de Microlectronique de Montpellier
[2] UMR 5506 - CC 477,undefined
来源：
Theory of Computing Systems | 2013年 / 52卷
关键词：
Kolmogorov complexity; Symmetry of information; Additivity of Kolmogorov complexity; Plain complexity;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
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.
引用
收藏
页码：297 / 302
页数：5
相关论文
共 50 条
12345