An Additivity Theorem for Plain Kolmogorov Complexity

被引：2

作者：

Bauwens, Bruno ^{[1
]}

Shen, Alexander ^{[2
]}

机构：

[1] Univ Porto, Fac Ciencia, Inst Telecomunicacoes, P-4169007 Oporto, Portugal

[2] Lab Informat Robot & Microlectron Montpellier, UMR 5506, CC 477, F-34095 Montpellier 5, France

来源：

THEORY OF COMPUTING SYSTEMS | 2013年 / 52卷 / 02期

关键词：

Kolmogorov complexity; Symmetry of information; Additivity of Kolmogorov complexity; Plain complexity;

D O I：

10.1007/s00224-012-9385-4

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We prove the formula C(a, b) = K(a vertical bar C(a, b)) + C(b vertical bar 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

页数：6

共 7 条

[1]

[Anonymous], 1989, Kolmogorov Complexity and Its Applications

[2] THEORY OF PROGRAM SIZE FORMALLY IDENTICAL TO INFORMATION-THEORY [J].

CHAITIN, GJ .

JOURNAL OF THE ACM, 1975, 22 (03) :329-340

[3]

Gacs P., 1988, LECT NOTES DESCRIPTI

[4]

Gacs P., 1974, Soviet Math. Dokl., V15, P1477

[5] 3 APPROACHES TO QUANTITATIVE DEFINITION OF INFORMATION [J].

KOLMOGOROV, AN .

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 1968, 2 (02) :157-+

[6] LOGICAL BASIS FOR INFORMATION THEORY AND PROBABILITY THEORY [J].

KOLMOGOROV, AN .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1968, 14 (05) :662-+

[7]

Shen A., 2000, TR2000034 UPPS U

← 1 →