Kolmogorov complexity and non-determinism

被引：0
|
作者：
Grigorieff, S
Marion, JY
机构：
[1] Univ Paris 07, UFR Informat, F-75251 Paris 05, France
[2] Univ Clermont Ferrand, Lab LLAIC, Clermont Ferrand, France
[3] Univ Nancy 2, LORIA, Calligramme Project, F-54506 Vandoeuvre Les Nancy, France
来源：
THEORETICAL COMPUTER SCIENCE | 2002年 / 271卷 / 1-2期
关键词：
Kolmogorov complexity;
D O I：
10.1016/S0304-3975(01)00038-X
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We are concerned with Kolmogorov complexity of strings produced by non-deterministic algorithms. For this, we consider five classes of non-deterministic description modes: (i) non-bounded description modes in which the number of outputs depends on programs, (ii) distributed description modes in which the number of outputs depends on the size of the outputs, (iii) spread description modes in which the number of outputs depends on both programs and the size of the outputs., (iv) description modes for which each string has a unique minimal description, and lastly (v) description modes for which the set of minimal length descriptions is a prefix set. (C) 2002 Elsevier Science B.V. All rights reserved.
引用
收藏
页码：151 / 180
页数：30
相关论文
共 50 条
  • [41] An Additivity Theorem for Plain Kolmogorov Complexity
    Bruno Bauwens
    Alexander Shen
    Theory of Computing Systems, 2013, 52 : 297 - 302
  • [42] List Approximation for Increasing Kolmogorov Complexity
    Zimand, Marius
    34TH SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2017), 2017, 66
  • [43] On the Approximation of the Kolmogorov Complexity for DNA Sequences
    Pratas, Diogo
    Pinho, Armando J.
    PATTERN RECOGNITION AND IMAGE ANALYSIS (IBPRIA 2017), 2017, 10255 : 259 - 266
  • [44] An Additivity Theorem for Plain Kolmogorov Complexity
    Bauwens, Bruno
    Shen, Alexander
    THEORY OF COMPUTING SYSTEMS, 2013, 52 (02) : 297 - 302
  • [45] Kolmogorov complexity conditional to large integers
    Vereshchagin, NK
    THEORETICAL COMPUTER SCIENCE, 2002, 271 (1-2) : 59 - 67
  • [46] Kolmogorov complexity for possibly infinite computations
    Becher V.
    Figueira S.
    Journal of Logic, Language and Information, 2005, 14 (2) : 133 - 148
  • [47] Fourier transform bounded Kolmogorov complexity
    Terry-Jack, Mohammed
    O'Keefe, Simon
    PHYSICA D-NONLINEAR PHENOMENA, 2023, 453
  • [48] Kolmogorov complexity and computably enumerable sets
    Barmpalias, George
    Li, Angsheng
    ANNALS OF PURE AND APPLIED LOGIC, 2013, 164 (12) : 1187 - 1200
  • [49] On the Kolmogorov complexity of continuous real functions
    Farjudian, Amin
    ANNALS OF PURE AND APPLIED LOGIC, 2013, 164 (05) : 566 - 576
  • [50] Information disclosure in the framework of Kolmogorov complexity
    Vereshchagin, Nikolay
    THEORETICAL COMPUTER SCIENCE, 2023, 940 : 108 - 122
12345