Base invariance of feasible dimension

DOI10.1016/j.ipl.2013.04.004zbMath1284.68309WikidataQ60578947 ScholiaQ60578947MaRDI QIDQ2444767

Elvira Mayordomo, John M. Hitchcock

Publication date: 11 April 2014

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2013.04.004

zbMATH Keywords

computational complexity; algorithmic information theory; effective dimension

Mathematics Subject Classification ID

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

28A80: Fractals

03D15: Complexity of computation (including implicit computational complexity)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

Algorithmic Fractal Dimensions in Geometric Measure Theory, Scaled dimension and the Kolmogorov complexity of Turing-hard sets, Effective Hausdorff dimension in general metric spaces, Feasible analysis, randomness, and base invariance, Base invariance of feasible dimension

Cites Work

• On normal numbers
• Entropy rates and finite-state dimension
• Almost everywhere high nonuniform complexity
• Fractal dimension and logarithmic loss unpredictability.
• Finite-state dimension
• The dimensions of individual strings and sequences
• Dimension is compression
• Base invariance of feasible dimension
• Dimension, entropy rates, and compression
• Endliche Automaten und Zufallsfolgen
• Effective fractal dimensions
• Algorithmic Randomness and Complexity
• Effective Strong Dimension in Algorithmic Information and Computational Complexity
• Dimension in Complexity Classes
• Unnamed Item
• Unnamed Item
• Unnamed Item