Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR06-070 | 23rd May 2006 00:00

The Kolmogorov complexity of infinite words

RSS-Feed




TR06-070
Authors: Ludwig Staiger
Publication: 31st May 2006 17:58
Downloads: 2949
Keywords: 


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 laid 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.



ISSN 1433-8092 | Imprint