scientific article
From MaRDI portal
Publication:4023358
zbMath0805.68063MaRDI QIDQ4023358
Publication date: 23 January 1993
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
algorithmic information theoryKolmogorov complexityinductive reasoningfoundations of statistical methods in physics
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) Measures of information, entropy (94A17) Axioms; other general questions in probability (60A05)
Related Items
Resource-bounded kolmogorov complexity revisited ⋮ Average-case analysis via incompressibility ⋮ Cellular automata universality revisited ⋮ Algorithmic arguments in physics of computation ⋮ Every 2-random real is Kolmogorov random ⋮ Weakly useful sequences ⋮ The combinatorial complexity of a finite string ⋮ Application of kolmogorov complexity to inductive inference with limited memory ⋮ Simple PAC learning of simple decision lists ⋮ Unnamed Item ⋮ Correlation and collective behaviour in Adler-type locally coupled oscillators at the edge of chaos ⋮ Randomness as an invariant for number representations ⋮ Some games on Turing machines and power from random strings ⋮ Cellular Automata: Descriptional Complexity and Decidability ⋮ Queue Automata: Foundations and Developments ⋮ Unnamed Item ⋮ A basis theorem for Π₁⁰ classes of positive measure and jump inversion for random reals ⋮ Transformations that preserve malignness of universal distributions ⋮ Gaining degrees of freedom in subsymbolic learning ⋮ Complexity through nonextensivity ⋮ Reversible pushdown transducers ⋮ Arithmetical representations of Brownian motion I ⋮ On algorithmic statistics for space-bounded algorithms ⋮ Summarizing and understanding large graphs ⋮ A Random Bag Preserving Product Operation ⋮ Unnamed Item ⋮ Boosting Reversible Pushdown and Queue Machines by Preprocessing ⋮ Enigma Variations: A Review Article ⋮ Abstract complexity theory and the \(\Delta_{2}^{0}\) degrees ⋮ The Borel-Cantelli lemmas, probability laws and Kolmogorov complexity ⋮ Exact complexity: the spectral decomposition of intrinsic computation ⋮ Kolmogorov complexity arguments in combinatorics ⋮ On reductions of NP sets to sparse sets ⋮ Computational depth and reducibility ⋮ Large sets in \(\mathrm{AC}^{0}\) have many strings with low Kolmogorov complexity ⋮ DNA sequencing and string learning ⋮ Graph compression and the zeros of polynomials ⋮ On Kurtz randomness ⋮ PACS, simple-PAC and query learning ⋮ The Kolmogorov complexity of random reals ⋮ Probabilities from entanglement, Born’s rule<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mml:mrow><mml:msub><mml:mi>p</mml:mi><mml:mi>k</mml:mi></mml:msub><mml:mo>=</mml:mo><mml:msup><mml:mrow><mml:mo>∣</mml:mo><mml:msub><mml:mi>ψ</mml:mi><mml:mi>k</mml:mi></mml:msub><mml:mo>∣</mml:mo></mml:mrow><mml:mn>2</mml:mn></mml:msup></mml:mrow></mml:math>from envariance ⋮ On reversible Turing machines and their function universality ⋮ Predictive rate-distortion for infinite-order Markov processes ⋮ Weinbaum factorizations of primitive words ⋮ On resource-bounded instance complexity ⋮ Lower bound technique for length-reducing automata ⋮ An excursion to the Kolmogorov random strings ⋮ Renormalisation and computation II: time cut-off and the Halting Problem ⋮ Kolmogorov-Loveland stochasticity for finite strings ⋮ The discovery of algorithmic probability ⋮ Learning recursive functions from approximations ⋮ Automatic Kolmogorov complexity, normality, and finite-state dimension revisited ⋮ An improved zero-one law for algorithmically random sequences ⋮ Some properties of antistochastic strings ⋮ Chaitin's omega and an algorithmic phase transition ⋮ Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension ⋮ Dimension 1 sequences are close to randoms ⋮ The Kolmogorov expressive power of Boolean query languages ⋮ Transformations that preserve malignness of universal distributions ⋮ Lempel-Ziv complexity analysis of one dimensional cellular automata ⋮ Predicting a binary sequence almost as well as the optimal biased coin ⋮ An oracle builder's toolkit ⋮ Krimp: mining itemsets that compress ⋮ On initial segment complexity and degrees of randomness ⋮ Exact constructive and computable dimensions ⋮ Summarizing categorical data by clustering attributes ⋮ Languages for gestalts of line patterns. ⋮ Prescribed Learning of R.E. Classes ⋮ Joint string complexity for Markov sources: small data matters ⋮ Unnamed Item ⋮ Feasible reductions to Kolmogorov-Loveland stochastic sequences ⋮ Complexity, randomness, discretization: some remarks on a program of J. Ford ⋮ Measures of statistical complexity: why? ⋮ The frequency interpretation in probability ⋮ On the approximation of shortest common supersequences and longest common subsequences ⋮ High end complexity ⋮ Inverse monoids associated with the complexity class NP ⋮ Learning in Friedberg numberings ⋮ On quasilinear-time complexity theory ⋮ A High-Low Kolmogorov Complexity Law equivalent to the 0-1 Law ⋮ Sub-classes of the monoid of left cancellative languages ⋮ Unreasonable effectiveness of symmetry in physics ⋮ On sets Turing reducible to p-selective sets ⋮ Pure quantum states are fundamental, mixtures (composite states) are mathematical constructions: An argument using algorithmic information theory ⋮ Lower time bounds for randomized computation ⋮ Schnorr trivial sets and truth-table reducibility ⋮ The upward closure of a perfect thin class ⋮ On explicating the concept `the power of an arithmetical theory' ⋮ Algorithmically independent sequences ⋮ Dynamics of a generic Brownian motion: Recursive aspects ⋮ Arithmetical Measure ⋮ On two-way communication in cellular automata with a fixed number of cells ⋮ On average sequence complexity ⋮ Turing degrees of reals of positive effective packing dimension ⋮ Effective dimension of points visited by Brownian motion ⋮ Two-Party Watson-Crick Computations ⋮ Models of knowing and the investigation of dynamical systems ⋮ Prescribed learning of r.e. classes ⋮ Polylog depth, highness and lowness for E ⋮ Transforming a single-valued transducer into a Mealy machine ⋮ A Hierarchy of Fast Reversible Turing Machines ⋮ Effective generation of subjectively random binary sequences ⋮ A game of prediction with expert advice ⋮ Succinct representation, leaf languages, and projection reductions ⋮ Sample size lower bounds in PAC learning by Algorithmic Complexity Theory ⋮ Ergodic theorems for individual random sequences ⋮ Reductions in circuit complexity: An isomorphism theorem and a gap theorem ⋮ Kolmogorov-Complexity Based on Infinite Computations ⋮ Randomness is inherently imprecise ⋮ Two Problems for Sophistication ⋮ On the computation of entropy prior complexity and marginal prior distribution for the Bernoulli model ⋮ On hard instances ⋮ A survey on interval routing ⋮ On the complexity of multi-dimensional interval routing schemes ⋮ On cognitive preferences and the plausibility of rule-based models ⋮ \(\mathcal{MOQA}\); unlocking the potential of compositional static average-case analysis ⋮ Effective symbolic dynamics, random points, statistical behavior, complexity and entropy ⋮ The Smyth Completion ⋮ The descriptive complexity of Brownian motion ⋮ What can be efficiently reduced to the Kolmogorov-random strings? ⋮ Kolmogorov complexity and symmetric relational structures ⋮ Optimization with randomized search heuristics -- the (A)NFL theorem, realistic scenarios, and difficult functions. ⋮ The impact of information on broadcasting time in linear radio networks. ⋮ Malign distributions for average case circuit complexity. ⋮ On the complexity of additive clustering models ⋮ Kolmogorov random graphs only have trivial stable colorings. ⋮ The Kolmogorov complexity of real numbers. ⋮ Predictions and algorithmic statistics for infinite sequences
