An introduction to Kolmogorov complexity and its applications

DOI10.1007/978-0-387-49820-1zbMath1185.68369OpenAlexW2582697902WikidataQ56626005 ScholiaQ56626005MaRDI QIDQ5900062

Paul M. B. Vitányi, Ming Li

Publication date: 4 June 2008

Published in: Texts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-0-387-49820-1

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Probability and inductive logic (03B48) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Foundations of equilibrium statistical mechanics (82B03) Axioms; other general questions in probability (60A05) Modulation and demodulation in information and communication theory (94A14)

Related Items (only showing first 100 items - show all)

Relating and contrasting plain and prefix Kolmogorov complexity ⋮ Compressibility and uniform complexity ⋮ Resource-bounded Kolmogorov complexity provides an obstacle to soficness of multidimensional shifts ⋮ Optimal self-assembly of finite shapes at temperature 1 in 3D ⋮ Mutual dimension and random sequences ⋮ Quantum logical depth and shallowness of streaming data by one-way quantum finite-state transducers (preliminary report) ⋮ Induction: a logical analysis ⋮ The entropy of a distributed computation random number generation from memory interleaving ⋮ Computable model discovery and high-level-programming approximations to algorithmic complexity ⋮ Kolmogorov complexity descriptions of the exquisite behaviors of advised deterministic pushdown automata ⋮ Open problems in universal induction \& intelligence ⋮ A complete theory of everything (will be subjective) ⋮ Clustering with respect to the information distance ⋮ Randomness? What randomness? ⋮ Regular patterns, regular languages and context-free languages ⋮ Lowness and logical depth ⋮ On the rate of decrease in logical depth ⋮ Conditional Kolmogorov complexity and universal probability ⋮ Universal knowledge-seeking agents ⋮ Succinct encoding of arbitrary graphs ⋮ A complexity approach to the soliton resolution conjecture ⋮ A divergence formula for randomness and dimension ⋮ Schnorr randomness for noncomputable measures ⋮ Dimension spectra of random subfractals of self-similar fractals ⋮ A philosophical treatise of universal induction ⋮ Stability of properties of Kolmogorov complexity under relativization ⋮ The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory ⋮ Control parameters for boundary-layer instabilities in unsteady shock interactions ⋮ A fast quartet tree heuristic for hierarchical clustering ⋮ A generalized characterization of algorithmic probability ⋮ Varieties of agents in agent-based computational economics: a historical and an interdisciplinary perspective ⋮ An additivity theorem for plain Kolmogorov complexity ⋮ Time-bounded Kolmogorov complexity and Solovay functions ⋮ One-way functions using algorithmic and classical information theories ⋮ Oscillation in the initial segment complexity of random reals ⋮ Test martingales, Bayes factors and \(p\)-values ⋮ On the computability of Solomonoff induction and AIXI ⋮ Low-depth witnesses are easy to find ⋮ An algorithmic look at financial volatility ⋮ Constraints placed on random sequences by their compressibility ⋮ Narrow big data in a stream: computational limitations and regression ⋮ Quantifying local randomness in human DNA and RNA sequences using Erdös motifs ⋮ Bounding the dimension of points on a line ⋮ An extended coding theorem with application to quantum complexities ⋮ Analogical proportions: from equality to inequality ⋮ Entropy measures vs. Kolmogorov complexity ⋮ Algorithmic relative complexity ⋮ Short lists for shortest descriptions in short time ⋮ The descriptive complexity of stochastic integration ⋮ Information complexity and applications. ⋮ Solovay functions and their applications in algorithmic randomness ⋮ Prefix and plain Kolmogorov complexity characterizations of 2-randomness: simple proofs ⋮ Anomalous learning helps succinctness ⋮ Revisiting Chaitin's incompleteness theorem ⋮ Rough set-based feature selection for weakly labeled data ⋮ Making sense of raw input ⋮ Fractal dimension versus process complexity ⋮ Covering the recursive sets ⋮ Algorithmic identification of probabilities is hard ⋮ Identification of probabilities ⋮ Brudno's theorem for \(\mathbb{Z}^d\) (or \(\mathbb{Z}_+^d\)) subshifts ⋮ Optimal staged self-assembly of general shapes ⋮ Sophistication vs logical depth ⋮ Numerical evaluation of algorithmic complexity for short strings: a glance into the innermost structure of randomness ⋮ Optimal program-size complexity for self-assembled squares at temperature 1 in 3D ⋮ A Kolmogorov complexity proof of the Lovász local lemma for satisfiability ⋮ Automatic learning of subclasses of pattern languages ⋮ Generalised entropies and asymptotic complexities of languages ⋮ Things that can be made into themselves ⋮ The frequent paucity of trivial strings ⋮ The equivalence of sampling and searching ⋮ Kolmogorov complexity and combinatorial methods in communication complexity ⋮ Time-universal data compression ⋮ Dimension spectra of lines ⋮ Connectedness properties of dimension level sets ⋮ Information measures for infinite sequences ⋮ On bounded redundancy of universal codes ⋮ Nonapproximability of the normalized information distance ⋮ Index sets and universal numberings ⋮ Constructing perfect steganographic systems ⋮ Correlation of automorphism group size and topological properties with program-size complexity evaluations of graphs and complex networks ⋮ Time-bounded incompressibility of compressible strings and sequences ⋮ Finite-state independence ⋮ Bounded Turing reductions and data processing inequalities for sequences ⋮ Algorithmic search in group theory ⋮ Microscopic reversibility and macroscopic irreversibility: from the viewpoint of algorithmic randomness ⋮ Searching for shortest and least programs ⋮ Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega ⋮ Ordered regions within a nonlinear time series solution of a Lorenz form of the Townsend equations for a boundary-layer flow ⋮ Expanding the algorithmic information theory frame for applications to Earth observation ⋮ Putnam's diagonal argument and the impossibility of a universal learning machine ⋮ A universal pair of 1/2-betting strategies ⋮ Normalized information distance and the oscillation hierarchy ⋮ Complexity-based permutation entropies: from deterministic time series to white noise ⋮ Randomness and initial segment complexity for measures ⋮ Uncertainty measures of rough set prediction ⋮ Learning (to disagree?) in large worlds ⋮ Measurable versions of the Lovász local lemma and measurable graph colorings ⋮ The teaching size: computable teachers and learners for universal languages ⋮ Hodology

This page was built for publication: An introduction to Kolmogorov complexity and its applications