The Kolmogorov complexity of infinite words

DOI10.1016/j.tcs.2007.04.013zbMath1124.68050MaRDI QIDQ2383593

Ludwig Staiger

Publication date: 19 September 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.04.013

zbMATH Keywords

Hausdorff dimension; Kolmogorov complexity; packing dimension; subword complexity; box-counting dimensions; \(\omega \)-languages; entropy of languages

Mathematics Subject Classification ID

68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)

Related Items

Unnamed Item, Few Paths, Fewer Words: Model Selection With Automatic Structure Functions, Finite state incompressible infinite sequences, On the complexity of a family of \(k\)-context-free sequences, Eulerian entropy and non-repetitive subword complexity, Kolmogorov structure functions for automatic complexity, Exact constructive and computable dimensions, Kolmogorov Structure Functions for Automatic Complexity in Computational Statistics, Drunken man infinite words complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Correspondence principles for effective dimensions
• Constructive dimension equals Kolmogorov complexity
• Combinatorial properties of the Hausdorff dimension
• The extent and density of sequences within the minimal-program complexity hierarchies
• The complexity and effectiveness of prediction algorithms
• On Hausdorff and topological dimensions of the Kolmogorov complexity of the real line
• A tight upper bound on Kolmogorov complexity and uniformly optimal prediction
• A generalization of Chaitin's halting probability \(\Omega\) and halting self-similar sets
• Noiseless coding of combinatorial sources, Hausdorff dimension, and Kolmogorov complexity
• The dimensions of individual strings and sequences
• Kolmogorov complexity and Hausdorff dimension
• Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. (Randomness and probability. An algorithmic foundation of probability theory)
• On partial randomness
• Finite state languages
• Von Mises' definition of random sequences reconsidered
• Minimal-program complexity of pseudo-recursive and pseudo-random sequences
• Dimension in Complexity Classes
• Compression and entropy
• STACS 2004
• On the Length of Programs for Computing Finite Binary Sequences
• Complexity oscillations in infinite binary sequences
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• The definition of random sequences
• A formal theory of inductive inference. Part I
• Developments in Language Theory
• Topological properties of omega context-free languages