Gales suffice for constructive dimension

DOI10.1016/S0020-0190(02)00454-4MaRDI QIDQ1007560zbMATH OpenFDO

Authors John M. Hitchcock

Publication date 23 March 2009

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

Full work available at URL https://doi.org/10.1016/S0020-0190(02)00454-4

zbMATH Keywords

computational complexityconstructive dimensiongales

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1670880
• STACS 2004
• The dimensions of individual strings and sequences
• A Characterization of Constructive Dimension
• A characterization of constructive dimension

Cites work

• A unified approach to the definition of random sequences
• Almost everywhere high nonuniform complexity
• scientific article; zbMATH DE number 1670880 (Why is no real title available?)
• scientific article; zbMATH DE number 2086652 (Why is no real title available?)
• 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
• Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. (Randomness and probability. An algorithmic foundation of probability theory)

Cited in

(9)

• Scaled dimension and the Kolmogorov complexity of Turing-hard sets
• Dimension extractors and optimal decompression
• The dimensions of individual strings and sequences
• Dimension, entropy rates, and compression
• scientific article; zbMATH DE number 1670880 (Why is no real title available?)
• A characterization of constructive dimension
• Random sequences with respect to a measure defined by two linear fractional transformations
• Algorithmic dimensions via learning functions
• Constructive dimension equals Kolmogorov complexity

This page was built for publication: Gales suffice for constructive dimension

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