Effective Hausdorff dimension in general metric spaces

DOI10.1007/S00224-018-9848-3zbMATH Open1436.03232arXiv1404.0077OpenAlexW2793162916WikidataQ60581653 ScholiaQ60581653MaRDI QIDQ1787953FDOQ1787953

Authors: Elvira Mayordomo 

Publication date: 5 October 2018

Published in: Theory of Computing Systems (Search for Journal in Brave)

Abstract: We introduce the concept of effective dimension for a wide class of metric spaces that are not required to have a computable measure. Effective dimension was defined by Lutz in (Lutz 2003) for Cantor space and has also been extended to Euclidean space. Lutz effectivization uses the concept of gale and supergale, our extension of Hausdorff dimension to other metric spaces is also based on a supergale characterization of dimension, which in practice avoids an extra quantifier present in the classical definition of dimension that is based on Hausdorff measure and therefore allows effectivization for small time-bounds. We present here the concept of constructive dimension and its characterization in terms of Kolmogorov complexity, for which we extend the concept of Kolmogorov complexity to any metric space defining the Kolmogorov complexity of a point at a certain precision. Further research directions are indicated.

Full work available at URL: https://arxiv.org/abs/1404.0077

Recommendations

• Effective dimension in some general metric spaces
• scientific article; zbMATH DE number 2222024
• Effective fractal dimensions
• Conditional dimension in metric spaces: a natural metric-space counterpart of Kolmogorov-complexity-based mutual dimension
• On a metric generalization of the \(tt\)-degrees and effective dimension theory

zbMATH Keywords

computable analysiseffective dimensionfractal geometryKolmogorov complexityalgorithmic randomness

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Hausdorff and packing measures (28A78) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Theory of numerations, effectively presented structures (03D45)

Cites Work

• Algorithmic randomness and complexity.
• Title not available (Why is that?)
• Noiseless coding of combinatorial sources, Hausdorff dimension, and Kolmogorov complexity
• Finite-state dimension
• The dimensions of individual strings and sequences
• Kolmogorov complexity and Hausdorff dimension
• Title not available (Why is that?)
• Computability of probability measures and Martin-Löf randomness over metric spaces
• Title not available (Why is that?)
• Dimensions of Points in Self-Similar Fractals
• Dimension in Complexity Classes
• Uniform test of algorithmic randomness over a general space
• A tight upper bound on Kolmogorov complexity and uniformly optimal prediction
• Symbolic dynamics: entropy = dimension = complexity
• Diagonally non-recursive functions and effective Hausdorff dimension
• Title not available (Why is that?)
• Title not available (Why is that?)
• On Hausdorff and topological dimensions of the Kolmogorov complexity of the real line
• Base invariance of feasible dimension
• Algorithmic information, plane Kakeya sets, and conditional dimension
• Algorithmic randomness over general spaces

Cited In (13)

• Effective fractal dimensions
• Conditional dimension in metric spaces: a natural metric-space counterpart of Kolmogorov-complexity-based mutual dimension
• On a metric generalization of the \(tt\)-degrees and effective dimension theory
• Extending the reach of the point-to-set principle
• Bounding the dimension of points on a line
• Algorithmic Fractal Dimensions in Geometric Measure Theory
• Asymptotic dimension, decomposition complexity, and Haver's property C
• Randomness and Effective Dimension of Continued Fractions.
• On continued fraction randomness and normality
• Effective dimension in some general metric spaces
• Effective zero-dimensionality for computable metric spaces
• The effective dimension of a set of measurement data
• Title not available (Why is that?)

This page was built for publication: Effective Hausdorff dimension in general metric spaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1787953)