Kolmogorov-Loveland Stochasticity and Kolmogorov Complexity

被引：1
作者：
Bienvenu, Laurent [1 ,2 ]
机构：
[1] Univ Aix Marseille 1, Lab Informat Fondamentale, F-13453 Marseille 13, France
[2] CNRS, F-13453 Marseille, France
来源：
THEORY OF COMPUTING SYSTEMS | 2010年 / 46卷 / 03期
关键词：
Kolmogorov complexity; Kolmogorov-Loveland stochasticity; Effective Hausdorff dimension; DIMENSION; RANDOMNESS; SEQUENCES;
D O I：
10.1007/s00224-009-9232-4
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
Merkle et al. ( Ann. Pure Appl. Logic 138(1-3): 183-210, 2006) showed that all Kolmogorov-Loveland stochastic infinite binary sequences have constructive Hausdorff dimension 1. In this paper, we go even further, showing that from an infinite sequence of dimension less than H(1/2+delta) ( H being the Shannon entropy function) one can extract by an effective selection rule a biased subsequence with bias at least delta. We also prove an analogous result for finite strings.
引用
收藏
页码：598 / 617
页数：20
相关论文
共 18 条
  • [1] AMBOSSPIES K, 1996, LECT NOTES COMPUTER, V1046, P63
  • [2] ASARIN EA, 1987, THEOR PROBAB APPL, V32, P507
  • [3] Downey R, 2005, LECT NOTES COMPUT SC, V3526, P96
  • [4] DOWNEY R, ALGORITHMIC RA UNPUB
  • [5] Kolmogorov-Loveland stochasticity for finite strings
    Durand, B
    Vereshchagin, N
    [J]. INFORMATION PROCESSING LETTERS, 2004, 91 (06) : 263 - 269
  • [6] Falconer K. J., 1985, Geometry of Fractal Sets
  • [7] Hausdorff F, 1919, MATH ANN, V79, P157
  • [8] Li M., 2008, An Introduction to Kolmogorov Complexity and Its Applications, V3rd
  • [9] The dimensions of individual strings and sequences
    Lutz, JH
    [J]. INFORMATION AND COMPUTATION, 2003, 187 (01) : 49 - 79
  • [10] Dimension in complexity classes
    Lutz, JH
    [J]. SIAM JOURNAL ON COMPUTING, 2003, 32 (05) : 1236 - 1259
12