Title: The Kolmogorov complexity of infinite words.
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.
Publication Year: 2006
Publication Date: 2006-01-01
Language: en
Type: article
Access and Citation
Cited By Count: 2
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot