On the Length of Programs for Computing Finite Binary Sequences

Cited in

(only showing first 100 items - show all)

On the notion of infinite pseudorandom sequences
On solving hard problems by polynomial-size circuits
Tape versus queue and stacks: The lower bounds
An unpredictability approach to finite-state randomness
Information dissipation in quantum-chaotic systems: Computational view and measurement induction
Complexity of algorithms and computations
Theory construction in psychology: The interpretation and integration of psychological data
Random languages for nonuniform complexity classes
Nonuniform complexity and the randomness of certain complete languages
Almost everywhere high nonuniform complexity
LISP program-size complexity
LISP program-size complexity. III
Circuit size relative to pseudorandom oracles
Automaton introspection
On the inference of optimal descriptions
Finite approximate approach to the study of the complexity of recursive predicates
Model discrimination using an algorithmic information criterion
Identifying randomness given by high descriptive complexity
Computational depth and reducibility
On Hausdorff and topological dimensions of the Kolmogorov complexity of the real line
The representation and manipulation of the algorithmic probability measure for problem solving.
The discovery of algorithmic probability
Stochastic complexity in learning
Quantifying complexity in the minority game
A catalog of Boolean concepts.
Information theory: A multifaceted model of information
Algorithmic complexity of recursive and inductive algorithms
The descriptive complexity of Brownian motion
A comparison of two approaches to pseudorandomness
The structural complexity of DNA templates -- implications on cellular complexity
Algorithmic complexity of quantum capacity
Open problems in universal induction \& intelligence
Complexity as a contrast between dynamics and phenomenology
On measuring the complexity of networks: Kolmogorov complexity versus entropy
Deflating the deflationary view of information
Sets with small generalized Kolmogorov complexity
Some consequences of the existnce of pseudorandom generators
Randomness on full shift spaces
Data compression and learning in time sequences analysis
Generation of symmetric exponential sums
The dimensions of individual strings and sequences
A network of autoregressive processing units for time series modeling
Axiomatizing Kolmogorov complexity
One-way functions using algorithmic and classical information theories
Simplicity and likelihood: an axiomatic approach
Physical complexity of symbolic sequences
Information and complexity, or: where is the information?
Thinking with notations: epistemic actions and epistemic activities in mathematical practice
Complexity study of \(q\)-deformed quantum harmonic oscillator
A comparison of Shannon, Kullback-Leibler and renormalized entropies within successive bifurcations
Infotropism as the underlying principle of perceptual organization
Cryptography and algorithmic randomness
The Kolmogorov complexity of infinite words
Algorithmic complexity as a criterion of unsolvability
On the advice complexity of the \(k\)-server problem
Comment on the Shiner-Davison-Landsberg measure
Entropy and quantum Kolmogorov complexity: a quantum Brudno's theorem
Dynamics of a generic Brownian motion: Recursive aspects
Subrecursive programming languages. II. On program size
Endliche Automaten und Zufallsfolgen
On graph entropy measures based on the number of independent sets and matchings
Real patterns and indispensability
Development of metrics and a complexity scale for the topology of assembly supply chains
A note on Blum static complexity measures
On the advice complexity of the k-server problem
THE FASTEST AND SHORTEST ALGORITHM FOR ALL WELL-DEFINED PROBLEMS
Towards an axiomatic system for Kolmogorov complexity
Kolmogorov complexity and probability measures.
Statistical learning theory, model identification and system information content
Gacs quantum algorithmic entropy in infinite dimensional Hilbert spaces
Algorithmic information theory and its statistical mechanical interpretation
Relations between information criteria for model-structure selection Part 2. Modelling by shortest data description
What is quantum information?
Degrees of monotone complexity
Sub-computable bounded pseudorandomness
QUANTUM KOLMOGOROV COMPLEXITY AND ITS APPLICATIONS
Approximate Entropy as an Irregularity Measure for Financial Data
Quantum algorithmic complexities and entropy
Justifying additive noise model-based causal discovery via algorithmic information theory
A generalized statistical complexity measure: applications to quantum systems
Kolmogorov-Complexity Based on Infinite Computations
Observations on the generation of permutations from random sequences
Asymptotical behaviour of some non-uniform measures
Genus distributions for iterated claws
Disentangling complexity from randomness and chaos
Minimal-program complexity of pseudo-recursive and pseudo-random sequences
APPROXIMATE, NON-DETERMINISTIC MODELLING OF BEHAVIOUR SEQUENCES
Quasi-Monte Carlo methods and pseudo-random numbers
Algorithmic complexity of points in dynamical systems
Not all (possibly) “random” sequences are created equal
Low-depth witnesses are easy to find
Information-theoretical complexity for the hydrogenic identity \(S_N2\) exchange reaction
Hierarchical approach to complexity with applications to dynamical systems
Convergence rates for the minimum complexity estimator of counting process intensities^∗
Entropy estimation of symbol sequences
Counting probability distributions: Differential geometry and model selection
Impugning randomness, convincingly
Computational depth and reducibility
Alan Turing and the foundation of computer science
A statistical complexity measure with nonextensive entropy and quasi-multiplicativity

This page was built for publication: On the Length of Programs for Computing Finite Binary Sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5541327)