Kolmogorov complexity and Hausdorff dimension

DOI10.1006/INCO.1993.1017zbMath0789.68076OpenAlexW2001496266MaRDI QIDQ2365758

Ludwig Staiger

Publication date: 29 June 1993

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.1993.1017

zbMATH Keywords

bibliographyHausdorff dimensionKolmogorov complexityrandom sequenceset entropy

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Hausdorff and packing measures (28A78)

Related Items (48)

Asymptotic Subword Complexity ⋮ Finite-state dimension ⋮ Constructive dimension equals Kolmogorov complexity ⋮ The dimensions of individual strings and sequences ⋮ A Correspondence Principle for Exact Constructive Dimension ⋮ Partial Randomness and Dimension of Recursively Enumerable Reals ⋮ The Kolmogorov complexity of infinite words ⋮ Local Hausdorff dimension ⋮ Natural halting probabilities, partial randomness, and zeta functions ⋮ Valuations, regular expressions, and fractal geometry ⋮ AVOIDING EFFECTIVE PACKING DIMENSION 1 BELOW ARRAY NONCOMPUTABLE C.E. DEGREES ⋮ Subword Metrics for Infinite Words ⋮ Exact constructive and computable dimensions ⋮ Dimension is compression ⋮ ALGORITHMS FOR FRACTAL DIMENSION CALCULATION ⋮ Algorithmically Independent Sequences ⋮ Fractal Intersections and Products via Algorithmic Dimension ⋮ Valuations and unambiguity of languages, with applications to fractal geometry ⋮ Algorithmic information theory and its statistical mechanical interpretation ⋮ Fractals, dimension, and formal languages ⋮ Subcomputable Hausdorff function dimension ⋮ Valuations of languages, with applications to fractal geometry ⋮ Refined Bounds on Kolmogorov Complexity for ω-Languages ⋮ On Oscillation-free ε-random Sequences ⋮ Error-correcting codes and phase transitions ⋮ Algorithmically independent sequences ⋮ Complex network dimension and path counts ⋮ Turing degrees of reals of positive effective packing dimension ⋮ Dimension, entropy rates, and compression ⋮ Representation of left-computable \(\varepsilon \)-random reals ⋮ Prediction and dimension ⋮ Liouville, computable, Borel normal and Martin-Löf random numbers ⋮ Effective Hausdorff dimension in general metric spaces ⋮ On universal computably enumerable prefix codes ⋮ INFINITE ITERATED FUNCTION SYSTEMS IN CANTOR SPACE AND THE HAUSDORFF MEASURE OF ω-POWER LANGUAGES ⋮ Unnamed Item ⋮ Scaled dimension and the Kolmogorov complexity of Turing-hard sets ⋮ Constructive Dimension and Hausdorff Dimension: The Case of Exact Dimension ⋮ Calibrating Randomness ⋮ On partial randomness ⋮ Kolmogorov-Loveland randomness and stochasticity ⋮ A Kolmogorov complexity characterization of constructive Hausdorff dimension. ⋮ Iterated function systems and control languages ⋮ Algorithmic Fractal Dimensions in Geometric Measure Theory ⋮ The Kolmogorov complexity of real numbers. ⋮ Finite state incompressible infinite sequences ⋮ Shift-invariant topologies for the Cantor space \(X^{\omega}\) ⋮ Entropy rates and finite-state dimension

This page was built for publication: Kolmogorov complexity and Hausdorff dimension