On the public citation graph
Relations Between Varieties of Kolmogorov Complexities
0 signed · 88 inferred · view as graph
Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.
Is this your work? Sign in with ORCID and put your name on the
claims that are yours.
Reference health. See whether every reference in this work resolves to a
known work and none has been retracted — and get a dated CiteStamped
badge you can embed.
What this work says
Outgoing claims: the papers this work cites, builds on, or argues with.
inferredcites →https://doi.org/10.1007/978-1-4757-3860-5openalex-snapshot
An Introduction to Kolmogorov Complexity and Its Applications
inferredcites →https://doi.org/10.1007/978-3-030-11298-1openalex-snapshot
An Introduction to Kolmogorov Complexity and Its Applications
inferredcites →https://doi.org/10.1007/978-3-642-77735-6openalex-snapshot
Kolmogorov Complexity and Computational Complexity
inferredcites →https://doi.org/10.1007/978-3-642-77735-6_6openalex-snapshot
Complexity and Entropy: An Introduction to the Theory of Kolmogorov Complexity
inferredcites →https://doi.org/10.1007/978-94-017-0837-1_12openalex-snapshot
A Survey of the Theory of Random Sequences
inferredcites →https://doi.org/10.1016/0304-3975(83)90139-1openalex-snapshot
On the relation between descriptional complexity and algorithmic probability
inferredcites →https://doi.org/10.1016/s0019-9958(64)90131-7openalex-snapshot
A formal theory of inductive inference. Part II
inferredcites →https://doi.org/10.1016/s0019-9958(64)90223-2openalex-snapshot
A formal theory of inductive inference. Part I
inferredcites →https://doi.org/10.1016/s0019-9958(69)90538-5openalex-snapshot
A variant of the Kolmogorov concept of complexity
inferredcites →https://doi.org/10.1016/s0022-0000(73)80030-3openalex-snapshot
Process complexity and effective random tests
inferredcites →https://doi.org/10.1017/cbo9780511608858openalex-snapshot
Algorithmic Information Theory
inferredcites →https://doi.org/10.1070/rm1970v025n06abeh001269openalex-snapshot
THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
inferredcites →https://doi.org/10.1070/rm1990v045n01abeh002321openalex-snapshot
Can an individual sequence of zeros and ones be random?
inferredcites →https://doi.org/10.1080/00207166808803030openalex-snapshot
Three approaches to the quantitative definition of information *
inferredcites →https://doi.org/10.1142/0531openalex-snapshot
Information, Randomness & Incompleteness
inferredcites →https://doi.org/10.1142/1048openalex-snapshot
Information, Randomness and Incompleteness
inferredcites →https://doi.org/10.1145/321356.321363openalex-snapshot
On the Length of Programs for Computing Finite Binary Sequences
inferredcites →https://doi.org/10.1145/321495.321506openalex-snapshot
On the Length of Programs for Computing Finite Binary Sequences
inferredcites →https://doi.org/10.1145/321892.321894openalex-snapshot
A Theory of Program Size Formally Identical to Information Theory
inferredcites →https://doi.org/10.2307/2274882openalex-snapshot
Gregory J. Chaitin, Algorithmic information theory, Cambridge tracts in theoretical computer science, no. 1. Cambridge University Press, Cambridge etc. 1987, xi + 175 pp.
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1006/jcss.1997.1517openalex-snapshot
Transforming a Single-Valued Transducer Into a Mealy Machine
inferred← citeshttps://doi.org/10.1006/jcss.1999.1677openalex-snapshot
Inequalities for Shannon Entropy and Kolmogorov Complexity
inferred← citeshttps://doi.org/10.1007/11564089_32openalex-snapshot
Monotone Conditional Complexity Bounds on Future Prediction Errors
inferred← citeshttps://doi.org/10.1007/11753728_29openalex-snapshot
Shannon Entropy vs. Kolmogorov Complexity
inferred← citeshttps://doi.org/10.1007/3-540-44683-4_22openalex-snapshot
Algorithmic Information Theory and Cellular Automata Dynamics
inferred← citeshttps://doi.org/10.1007/3-540-49116-3_14openalex-snapshot
Descriptive Complexity of Computable Sequences
inferred← citeshttps://doi.org/10.1007/3-540-61550-4_145openalex-snapshot
Kolmogorov complexity: Recent research in Moscow
inferred← citeshttps://doi.org/10.1007/978-3-642-13182-0_25openalex-snapshot
Monotone Complexity of a Pair
inferred← citeshttps://doi.org/10.1007/978-3-642-22953-4_22openalex-snapshot
Constructive Dimension and Hausdorff Dimension: The Case of Exact Dimension
inferred← citeshttps://doi.org/10.1007/978-3-642-27654-5_15openalex-snapshot
On Oscillation-Free Chaitin h-Random Sequences
inferred← citeshttps://doi.org/10.1007/978-3-642-30870-3_69openalex-snapshot
A Correspondence Principle for Exact Constructive Dimension
inferred← citeshttps://doi.org/10.1007/978-3-662-55751-8_33openalex-snapshot
Automatic Kolmogorov Complexity and Normality Revisited
inferred← citeshttps://doi.org/10.1007/978-94-010-0920-1_5openalex-snapshot
Why Kolmogorov Complexity?
inferred← citeshttps://doi.org/10.1007/bfb0055824openalex-snapshot
Comparison between the complexity of a function and the complexity of its graph
inferred← citeshttps://doi.org/10.1007/s00224-014-9546-8openalex-snapshot
Symbolic Dynamics: Entropy = Dimension = Complexity
inferred← citeshttps://doi.org/10.1007/s00224-017-9790-9openalex-snapshot
Exact Constructive and Computable Dimensions
inferred← citeshttps://doi.org/10.1007/s10884-026-10487-1openalex-snapshot
On the Entropic Chaos Degree and Orbit Complexities
inferred← citeshttps://doi.org/10.1007/s11786-010-0031-8openalex-snapshot
Error-Correcting Codes and Phase Transitions
inferred← citeshttps://doi.org/10.1016/j.apal.2011.06.010openalex-snapshot
Martin-Löf randomness and Galton–Watson processes
inferred← citeshttps://doi.org/10.1016/j.apal.2013.10.006openalex-snapshot
Propagation of partial randomness
inferred← citeshttps://doi.org/10.1016/j.apal.2015.03.001openalex-snapshot
Cone avoidance and randomness preservation
inferred← citeshttps://doi.org/10.1016/j.entcs.2004.06.037openalex-snapshot
Orbit Complexity and Entropy for Group Endomorphisms
inferred← citeshttps://doi.org/10.1016/j.entcs.2008.12.016openalex-snapshot
Refined Bounds on Kolmogorov Complexity for ω-Languages
inferred← citeshttps://doi.org/10.1016/j.entcs.2008.12.024openalex-snapshot
On Oscillation-free ε-random Sequences
inferred← citeshttps://doi.org/10.1016/j.ic.2006.10.004openalex-snapshot
Algorithmic complexity bounds on future prediction errors
inferred← citeshttps://doi.org/10.1016/j.ic.2010.10.003openalex-snapshot
Algorithmic randomness and monotone complexity on product space
inferred← citeshttps://doi.org/10.1016/j.ipl.2004.09.023openalex-snapshot
Constructive dimension equals Kolmogorov complexity
inferred← citeshttps://doi.org/10.1016/j.jcss.2007.03.015openalex-snapshot
Individual communication complexity
inferred← citeshttps://doi.org/10.1016/j.jcss.2020.12.003openalex-snapshot
Automatic Kolmogorov complexity, normality, and finite-state dimension revisited
inferred← citeshttps://doi.org/10.1016/j.physa.2018.04.025openalex-snapshot
Entropy of high-order Markov chains beyond the pair correlations
inferred← citeshttps://doi.org/10.1016/j.tcs.2012.03.007openalex-snapshot
A linearly computable measure of string complexity
inferred← citeshttps://doi.org/10.1016/j.tcs.2020.01.013openalex-snapshot
Descriptive complexity of computable sequences revisited
inferred← citeshttps://doi.org/10.1016/s0304-3975(00)00012-8openalex-snapshot
Kolmogorov complexity and cellular automata classification
inferred← citeshttps://doi.org/10.1016/s0304-3975(01)00028-7openalex-snapshot
Kolmogorov entropy in the context of computability theory
inferred← citeshttps://doi.org/10.1016/s0304-3975(01)00029-9openalex-snapshot
Comparison between the complexity of a function and the complexity of its graph
inferred← citeshttps://doi.org/10.1016/s0304-3975(01)00030-5openalex-snapshot
Descriptive complexity of computable sequences
inferred← citeshttps://doi.org/10.1016/s0304-3975(01)00034-2openalex-snapshot
Combinatorial interpretation of Kolmogorov complexity
inferred← citeshttps://doi.org/10.1016/s0304-3975(01)00038-xopenalex-snapshot
Kolmogorov complexity and non-determinism
inferred← citeshttps://doi.org/10.1016/s0304-3975(02)00847-2openalex-snapshot
Almost periodic sequences
inferred← citeshttps://doi.org/10.1016/s0304-3975(98)00069-3openalex-snapshot
Mathematical metaphysics of randomness
inferred← citeshttps://doi.org/10.1017/jsl.2013.7openalex-snapshot
MASS PROBLEMS AND INITIAL SEGMENT COMPLEXITY
inferred← citeshttps://doi.org/10.1023/a:1023638717091openalex-snapshot
On the Role of the Law of Large Numbers in the Theory of Randomness
inferred← citeshttps://doi.org/10.1090/s0002-9947-2011-05315-8openalex-snapshot
Increasing the gap between descriptional complexity and algorithmic probability
inferred← citeshttps://doi.org/10.1093/comjnl/42.4.294openalex-snapshot
Algorithmic Complexity and Stochastic Properties of Finite Binary Sequences
inferred← citeshttps://doi.org/10.1093/comjnl/42.4.340openalex-snapshot
Discussion on Kolmogorov Complexity and Statistical Analysis
inferred← citeshttps://doi.org/10.1103/physreve.96.012158openalex-snapshot
Decomposition of conditional probability for high-order symbolic Markov chains
inferred← citeshttps://doi.org/10.1109/ccc.1997.612296openalex-snapshot
Inequalities for Shannon entropies and Kolmogorov complexities
inferred← citeshttps://doi.org/10.1109/ccc.2009.13openalex-snapshot
Increasing the Gap between Descriptional Complexity and Algorithmic Probability
inferred← citeshttps://doi.org/10.1134/s0032946010010059openalex-snapshot
Stability of properties of Kolmogorov complexity under relativization
inferred← citeshttps://doi.org/10.1134/s1064226911060210openalex-snapshot
Development of the algorithmic information theory in Russia
inferred← citeshttps://doi.org/10.1137/s0040585x97980865openalex-snapshot
On the Concept of Random Sequence with Respect to p -Adic Valued Probabilities
inferred← citeshttps://doi.org/10.1305/ndjfl/1107220673openalex-snapshot
Program Size Complexity for Possibly Infinite Computations
inferred← citeshttps://doi.org/10.2178/jsl/1164060458openalex-snapshot
Degrees of monotone complexity
inferred← citeshttps://doi.org/10.26686/wgtn.16985293.v1openalex-snapshot
Randomness and Computability
inferred← citeshttps://doi.org/10.3390/axioms10040306openalex-snapshot
The Maximal Complexity of Quasiperiodic Infinite Words
inferred← citeshttps://doi.org/10.4213/tvp236openalex-snapshot
О концепции случайной последовательности относительно $p$-адических вероятностей
inferred← citeshttps://doi.org/10.4230/dagsemproc.06051.6openalex-snapshot
Complexity Monotone in Conditions and Future Prediction Errors
inferred← citeshttps://doi.org/10.4230/lipics.mfcs.2018.2openalex-snapshot
Plain Stopping Time and Conditional Complexities Revisited
inferred← citeshttps://doi.org/10.4337/9781781952665.00009openalex-snapshot
A Computable Economist’s Perspective on Computational Complexity
inferred← citeshttps://doi.org/10.48550/arxiv.1012.0232openalex-snapshot
Kolmogorov-Loveland Sets and Advice Complexity Classes
inferred← citeshttps://doi.org/10.48550/arxiv.1310.3091openalex-snapshot
A generalization of Levin-Schnorr's theorem
inferred← citeshttps://doi.org/10.48550/arxiv.1701.09060openalex-snapshot
Automatic Kolmogorov complexity, normality and finite state dimension revisited
inferred← citeshttps://doi.org/10.48550/arxiv.1702.04394openalex-snapshot
Symbolic dynamics: entropy = dimension = complexity
inferred← citeshttps://doi.org/10.48550/arxiv.2008.02773openalex-snapshot
Mathematical works of Vladimir A. Uspensky: A commentary
Editorial review for independent work. ICSAC — the Institute for Complexity
Science and Advanced Computing — runs a structured editorial panel for researchers
publishing outside journals, and publishes on CiteStamp rails. Submission is free
and goes through ORCID: icsacinstitute.org/submit.