| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 438337 | Theoretical Computer Science | 2007 | 13 Pages |
Abstract
We present a brief survey of results on relations between the Kolmogorov complexity of infinite strings and several measures of information content (dimensions) known from dimension theory, information theory or fractal geometry.Special emphasis is placed on bounds on the complexity of strings in constructively given subsets of the Cantor space. Finally, we compare the Kolmogorov complexity to the subword complexity of infinite strings.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
