scientific article; zbMATH DE number 1010621

Publication date: 19 May 1997

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

computational complexity data compression Kolmogorov complexity computational learning instance complexity circuit theory universal prediction CD compression distributed algorithmics Kolmogorov random graphs shortest encoding

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) Measures of information, entropy (94A17) Axioms; other general questions in probability (60A05)

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

Complementarity of information obtained by Kolmogorov and Aksentijevic-Gibson complexities in the analysis of binary time series ⋮ On a nonstandard Brownian motion and its maximal function ⋮ Randomness and reducibility ⋮ Succinct definitions in the first order theory of graphs ⋮ Generality's price: Inescapable deficiencies in machine-learned programs ⋮ Computational depth: Concept and applications ⋮ NL-printable sets and nondeterministic Kolmogorov complexity ⋮ Recursion and topology on \(2^{\leq\omega}\) for possibly infinite computations ⋮ The dimensions of individual strings and sequences ⋮ Average-case analysis of quicksort and binary insertion tree height using incompressibility ⋮ On semimeasures predicting Martin-Löf random sequences ⋮ On universal prediction and Bayesian confirmation ⋮ Non-reducible descriptions for conditional Kolmogorov complexity ⋮ `Ideal learning' of natural language: positive results about learning from positive evidence ⋮ The Kolmogorov complexity of infinite words ⋮ Is complexity a source of incompleteness? ⋮ A coding theorem for enumerable output machines ⋮ Sublinear algorithms for approximating string compressibility ⋮ Differences of halting probabilities ⋮ Optimal redundancy in computations from random oracles ⋮ Learning secrets interactively. Dynamic modeling in inductive inference ⋮ Identifying shapes using self-assembly ⋮ A calculus for measuring the elegance of abstract graphs ⋮ Reducing tile complexity for the self-assembly of scaled shapes through temperature programming ⋮ Does inducing choice procedures make individuals better off? An experimental study ⋮ On the paper of Pascal Schweitzer concerning similarities between incompressibility methods and the Lovász local lemma ⋮ Characterization of Kurtz randomness by a differentiation theorem ⋮ Comment on the Shiner-Davison-Landsberg measure ⋮ Weighted relative entropy for phylogenetic tree based on 2-step Markov model ⋮ Using the minimum description length to discover the intrinsic cardinality and dimensionality of time series ⋮ Limit complexities revisited ⋮ Universal construction mechanism for networks from one-dimensional symbol sequences ⋮ Random reals à la Chaitin with or without prefix-freeness ⋮ Model selection based on minimum description length ⋮ New applications of the incompressibility method. II ⋮ Finite-state dimension and real arithmetic ⋮ Accelerating the discovery of unsupervised-shapelets ⋮ Classification of streaming time series under more realistic assumptions ⋮ The PRIMPING routine -- tiling through proximal alternating linearized minimization ⋮ The complexities of nonperturbative computations ⋮ Compressibility, laws of nature, initial conditions and complexity ⋮ The complexity of stochastic sequences ⋮ Lowness properties and approximations of the jump ⋮ Improving the space-bounded version of Muchnik's conditional complexity theorem via ``naive derandomization ⋮ The cost of offline binary search tree algorithms and the complexity of the request sequence ⋮ The equivalence between ordinal optimization in deterministic complex problems and in stochastic simulation problems ⋮ Evolutionary induction of stochastic context free grammars ⋮ The asymptotic equipartition property in reinforcement learning and its relation to return maximization ⋮ Infotropism as the underlying principle of perceptual organization ⋮ Does the polynomial hierarchy collapse if onto functions are invertible? ⋮ Distance measures for biological sequences: some recent approaches ⋮ Weakly useful sequences ⋮ On the computational power of random strings ⋮ Different faces of chaos in FRW models with scalar fields -- geometrical point of view ⋮ An algebra of human concept learning ⋮ Kolmogorov complexity for possibly infinite computations ⋮ Improved metaheuristics for the quartet method of hierarchical clustering ⋮ Effective bounds for convergence, descriptive complexity, and natural examples of simple and hypersimple sets ⋮ Predictive complexity and information ⋮ Local realistic representation for correlations in the original EPR-model for position and momentum ⋮ Complexity analysis of the turbulent environmental fluid flow time series ⋮ Application of Kolmogorov complexity and universal codes to identity testing and nonparametric testing of serial independence for time series ⋮ Equivalences between learning of data and probability distributions, and their applications ⋮ Accumulative prediction error and the selection of time series models ⋮ Model selection by normalized maximum likelihood ⋮ An exact algorithm for the minimum quartet tree cost problem ⋮ On the complexity of the smallest grammar problem over fixed alphabets ⋮ Construction of sequences of zeros and ones with complex finite sequences ⋮ Data compression and genomes: a two-dimensional life domain map ⋮ Descriptive complexity of computable sequences revisited ⋮ When-and how-can a cellular automaton be rewritten as a lattice gas? ⋮ Monotonous betting strategies in warped casinos ⋮ Algorithmic networks: central time to trigger expected emergent open-endedness ⋮ On the computational complexity of Longley's \(H\) functional ⋮ Weak completeness notions for exponential time ⋮ A discipline of evolutionary programming ⋮ DNA combinatorial messages and epigenomics: the case of chromatin organization and nucleosome occupancy in eukaryotic genomes ⋮ Uniform test of algorithmic randomness over a general space ⋮ How many strings are easy to predict? ⋮ Martin-Löf randomness implies multiple recurrence in effectively closed sets ⋮ Applying MDL to learn best model granularity ⋮ Information and complexity, or: where is the information? ⋮ Average-case analysis of algorithms using Kolmogorov complexity ⋮ A Kolmogorov complexity characterization of constructive Hausdorff dimension. ⋮ Prediction algorithms and confidence measures based on algorithmic randomness theory. ⋮ Martin's game: a lower bound for the number of sets. ⋮ Recursive computational depth. ⋮ Most sequences are stochastic ⋮ Suboptimal measures of predictive complexity for absolute loss function ⋮ On complexity of easy predictable sequences ⋮ Unpredictability of complex (pure) strategies ⋮ Information theory, evolution and the origin of life ⋮ Analyzing variants of Shellsort ⋮ Bounds for the Element Distinctness Problem on one-tape Turing machines ⋮ Does snooping help? ⋮ Conformal predictions for information fusion. A comparative study of p-value combination methods ⋮ Effective simultaneous approximability of reals. ⋮ Randomness on full shift spaces ⋮ Algorithmic analysis of irrational rotations in a single neuron model ⋮ Data compression and learning in time sequences analysis

This page was built for publication: