Relations between varieties of kolmogorov complexities

DOI10.1007/BF01201280zbMath0849.68059OpenAlexW2571335838MaRDI QIDQ4879210

Alexander Shen, Vladimir A. Uspensky

Publication date: 29 July 1996

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01201280

zbMATH Keywords

Kolmogorov complexity

Mathematics Subject Classification ID

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

Related Items (36)

On Oscillation-Free Chaitin h-Random Sequences ⋮ Constructive dimension equals Kolmogorov complexity ⋮ A Correspondence Principle for Exact Constructive Dimension ⋮ Entropy of high-order Markov chains beyond the pair correlations ⋮ Individual communication complexity ⋮ MASS PROBLEMS AND INITIAL SEGMENT COMPLEXITY ⋮ Algorithmic complexity bounds on future prediction errors ⋮ Automatic Kolmogorov complexity, normality, and finite-state dimension revisited ⋮ Propagation of partial randomness ⋮ Stability of properties of Kolmogorov complexity under relativization ⋮ Almost periodic sequences. ⋮ Exact constructive and computable dimensions ⋮ Algorithmic randomness and monotone complexity on product space ⋮ Unnamed Item ⋮ A linearly computable measure of string complexity ⋮ Refined Bounds on Kolmogorov Complexity for ω-Languages ⋮ On Oscillation-free ε-random Sequences ⋮ Error-correcting codes and phase transitions ⋮ Kolmogorov complexity and cellular automata classification ⋮ Program size complexity for possibly infinite computations ⋮ Kolmogorov entropy in the context of computability theory ⋮ Comparison between the complexity of a function and the complexity of its graph ⋮ Descriptive complexity of computable sequences ⋮ Combinatorial interpretation of Kolmogorov complexity ⋮ Kolmogorov complexity and non-determinism ⋮ Descriptive complexity of computable sequences revisited ⋮ Constructive Dimension and Hausdorff Dimension: The Case of Exact Dimension ⋮ Transforming a single-valued transducer into a Mealy machine ⋮ Increasing the gap between descriptional complexity and algorithmic probability ⋮ Mathematical metaphysics of randomness ⋮ Martin-Löf randomness and Galton-Watson processes ⋮ Inequalities for Shannon entropy and Kolmogorov complexity ⋮ Degrees of monotone complexity ⋮ On partial randomness ⋮ Cone avoidance and randomness preservation ⋮ Symbolic dynamics: entropy = dimension = complexity

Cites Work

• On the relation between descriptional complexity and algorithmic probability
• Process complexity and effective random tests
• Can an individual sequence of zeros and ones be random?
• Algorithmic Information Theory
• A Theory of Program Size Formally Identical to Information Theory
• On the Length of Programs for Computing Finite Binary Sequences
• On the Length of Programs for Computing Finite Binary Sequences
• A variant of the Kolmogorov concept of complexity
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• A formal theory of inductive inference. Part I
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Relations between varieties of kolmogorov complexities