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 条
  • [21] On the Formalisation of Kolmogorov Complexity
    Catt, Elliot
    Norrish, Michael
    CPP '21: PROCEEDINGS OF THE 10TH ACM SIGPLAN INTERNATIONAL CONFERENCE ON CERTIFIED PROGRAMS AND PROOFS, 2021, : 291 - 299
  • [22] Kolmogorov complexity and combinatorial methods in communication complexity
    Kaplan, Marc
    Laplante, Sophie
    THEORETICAL COMPUTER SCIENCE, 2011, 412 (23) : 2524 - 2535
  • [23] KOLMOGOROV COMPLEXITY AND RANDOM GRAPHS
    KIRCHHERR, WW
    INFORMATION PROCESSING LETTERS, 1992, 41 (03) : 125 - 130
  • [24] The Kolmogorov complexity of random reals
    Yu, L
    Ding, DC
    Downey, R
    ANNALS OF PURE AND APPLIED LOGIC, 2004, 129 (1-3) : 163 - 180
  • [25] A SIMPLE MEASURE OF THE KOLMOGOROV COMPLEXITY
    Ivanko, Evgeny
    KDIR 2009: PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON KNOWLEDGE DISCOVERY AND INFORMATION RETRIEVAL, 2009, : 5 - 9
  • [26] Topological Arguments for Kolmogorov Complexity
    Andrei Romashchenko
    Alexander Shen
    Theory of Computing Systems, 2015, 56 : 513 - 526
  • [27] Kolmogorov Complexity as a Combinatorial Tool
    Shen, Alexander
    TWENTY YEARS OF THEORETICAL AND PRACTICAL SYNERGIES, CIE 2024, 2024, 14773 : 27 - 31
  • [28] Combinatorial interpretation of Kolmogorov complexity
    Romashchenko, A
    Shen, A
    Vereshchagin, N
    THEORETICAL COMPUTER SCIENCE, 2002, 271 (1-2) : 111 - 123
  • [29] Topological Arguments for Kolmogorov Complexity
    Romashchenko, Andrei
    Shen, Alexander
    THEORY OF COMPUTING SYSTEMS, 2015, 56 (03) : 513 - 526
  • [30] The axiomatic power of Kolmogorov complexity
    Bienvenu, Laurent
    Romashchenko, Andrei
    Shen, Alexander
    Taveneaux, Antoine
    Vermeeren, Stijn
    ANNALS OF PURE AND APPLIED LOGIC, 2014, 165 (09) : 1380 - 1402
12345