A Kolmogorov complexity characterization of constructive Hausdorff dimension

被引：93

作者：

Mayordomo, E ^{[1
]}

机构：

[1] Univ Zaragoza, Dept Informat & Ingn Sistemas, Zaragoza 50015, Spain

来源：

INFORMATION PROCESSING LETTERS | 2002年 / 84卷 / 01期

关键词：

Kolmogorov complexity; information theory; Hausdorff dimension; theory of computation;

D O I：

10.1016/S0020-0190(02)00343-5

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

A constructive version of Hausdorff dimension using Kolmogorov complexity was developed. Classical Hausdorff dimension is an augmentation of Lebesgue measure and the constructive dimension augments Martin-Löf randomness. The characterization of constructive dimension was obtained in terms of algorithmic information content.

引用

页码：1 / 3

页数：3

共 10 条

[1]

CHAITIN G, 1987, ALGORITHMIC INFORMAT

[2]

Falconer K. J., 1985, The geometry of fractal sets

[3]

Hausdorff F, 1919, MATH ANN, V79, P157

[4]

LI M, 1997, INTRO KOLMOGOROV COM

[5]

Lutz JH, 2000, LECT NOTES COMPUT SC, V1853, P902

[6] Dimension in complexity classes [J].

Lutz, JH .

15TH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, PROCEEDINGS, 2000, :158-169

[7]

LUTZ JH, 2002, CSCC0203017 ACM COMP

[8]

Ryabko B. Ya., 1994, Journal of Complexity, V10, P281, DOI 10.1006/jcom.1994.1015

[9] A tight upper bound on Kolmogorov complexity and uniformly optimal prediction [J].

Staiger, L .

THEORY OF COMPUTING SYSTEMS, 1998, 31 (03) :215-229

[10] KOLMOGOROV COMPLEXITY AND HAUSDORFF DIMENSION [J].

STAIGER, L .

INFORMATION AND COMPUTATION, 1993, 103 (02) :159-194

← 1 →