Relations between varieties of kolmogorov complexities
From MaRDI portal
Publication:4879210
DOI10.1007/BF01201280zbMATH Open0849.68059OpenAlexW2571335838MaRDI QIDQ4879210FDOQ4879210
Authors: A. Shen, V. A. Uspenskiĭ 
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
Recommendations
Cites Work
- Title not available (Why is that?)
- On the Length of Programs for Computing Finite Binary Sequences
- A formal theory of inductive inference. Part I
- Process complexity and effective random tests
- Algorithmic Information Theory
- A Theory of Program Size Formally Identical to Information Theory
- THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the Length of Programs for Computing Finite Binary Sequences
- On the relation between descriptional complexity and algorithmic probability
- A variant of the Kolmogorov concept of complexity
- Information, randomness and incompleteness. Papers on algorithmic information theory
- Can an individual sequence of zeros and ones be random?
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (42)
- Program size complexity for possibly infinite computations
- On Oscillation-Free Chaitin h-Random Sequences
- A Correspondence Principle for Exact Constructive Dimension
- Error-correcting codes and phase transitions
- Automatic Kolmogorov complexity, normality, and finite-state dimension revisited
- Descriptive complexity of computable sequences revisited
- Algorithmic complexity bounds on future prediction errors
- Kolmogorov's complexity for positive definite matrices
- Constructive dimension equals Kolmogorov complexity
- Transforming a single-valued transducer into a Mealy machine
- Relating and contrasting plain and prefix Kolmogorov complexity
- Increasing the gap between descriptional complexity and algorithmic probability
- Kolmogorov complexity and cellular automata classification
- Title not available (Why is that?)
- Degrees of monotone complexity
- Symbolic dynamics: entropy = dimension = complexity
- Prefix-free and prefix-correct complexities with compound conditions
- A linearly computable measure of string complexity
- Kolmogorov entropy in the context of computability theory
- On oscillation-free \(\varepsilon\)-random sequences
- Descriptive complexity of computable sequences
- Title not available (Why is that?)
- Title not available (Why is that?)
- Refined Bounds on Kolmogorov Complexity for ω-Languages
- Entropy of high-order Markov chains beyond the pair correlations
- Mathematical metaphysics of randomness
- Mass problems and initial segment complexity
- Inequalities for Shannon entropy and Kolmogorov complexity
- Individual communication complexity
- Stability of properties of Kolmogorov complexity under relativization
- On partial randomness
- Combinatorial interpretation of Kolmogorov complexity
- Almost periodic sequences.
- Cone avoidance and randomness preservation
- Martin-Löf randomness and Galton-Watson processes
- Exact constructive and computable dimensions
- Constructive dimension and Hausdorff dimension: the case of exact dimension
- Entropy measures vs. Kolmogorov complexity
- Kolmogorov complexity and non-determinism
- Comparison between the complexity of a function and the complexity of its graph
- Algorithmic randomness and monotone complexity on product space
- Propagation of partial randomness
This page was built for publication: Relations between varieties of kolmogorov complexities
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4879210)
