The Kolmogorov complexity of infinite words

DOI10.1016/j.tcs.2007.04.013zbMath1124.68050OpenAlexW1997534682MaRDI 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 dimensionKolmogorov complexitypacking dimensionsubword complexitybox-counting dimensions\(\omega \)-languagesentropy of languages

Mathematics Subject Classification ID

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

Related Items

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

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