The dimensions of individual strings and sequences

DOI10.1016/S0890-5401(03)00187-1zbMath1090.68053MaRDI QIDQ1887139

Jack H. Lutz

Publication date: 23 November 2004

Published in: Information and Computation (Search for Journal in Brave)

zbMATH Keywords

Hausdorff dimensionKolmogorov complexityKullback-Leibler divergenceComputabilityEntropyMartingalesRandomnessDimensionGalesAlgorithmic informationConstructive dimensionSupergalesTermgales

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Related Items

Scaled dimension and nonuniform complexity, Finite-state dimension, Constructive dimension equals Kolmogorov complexity, A Correspondence Principle for Exact Constructive Dimension, Mutual dimension and random sequences, The Kolmogorov complexity of infinite words, Natural halting probabilities, partial randomness, and zeta functions, Automatic Kolmogorov complexity, normality, and finite-state dimension revisited, AVOIDING EFFECTIVE PACKING DIMENSION 1 BELOW ARRAY NONCOMPUTABLE C.E. DEGREES, On continued fraction randomness and normality, A divergence formula for randomness and dimension, Dimension spectra of random subfractals of self-similar fractals, Strict process machine complexity, The Kučera-Gács theorem revisited by Levin, Effective Dimensions and Relative Frequencies, Exact constructive and computable dimensions, Dimensions of Points in Self-similar Fractals, Dimension is compression, Bounded Pushdown Dimension vs Lempel Ziv Information Density, Connectivity properties of dimension level sets, ALGORITHMS FOR FRACTAL DIMENSION CALCULATION, Base invariance of feasible dimension, Algorithmically Independent Sequences, Bounding the dimension of points on a line, Effective packing dimension of $\Pi ^0_1$-classes, Effective dimensions and relative frequencies, Representation of maxitive measures: An overview, Martingale families and dimension in P, Computability theory. Abstracts from the workshop held January 7--13, 2018, Who Asked Us? How the Theory of Computing Answers Questions about Analysis, Finite-state dimension and real arithmetic, Random sequences with respect to a measure defined by two linear fractional transformations, Subcomputable Hausdorff function dimension, Fractal dimension versus process complexity, The power of backtracking and the confinement of length, Generic density and small span theorem, Effectively closed sets of measures and randomness, A Divergence Formula for Randomness and Dimension, Algorithmically independent sequences, Kolmogorov-Loveland stochasticity and Kolmogorov complexity, Dimension spectra of lines, Connectedness properties of dimension level sets, Complex network dimension and path counts, Turing degrees of reals of positive effective packing dimension, Dimension, entropy rates, and compression, Extracting Kolmogorov complexity with applications to dimension zero-one laws, Prediction and dimension, Two sources are better than one for increasing the Kolmogorov complexity of infinite sequences, A note on dimensions of polynomial size circuits, Bounded Turing reductions and data processing inequalities for sequences, Effective Hausdorff dimension in general metric spaces, Pushdown dimension, Constructive dimension and Turing degrees, A characterization of constructive dimension, Scaled dimension and the Kolmogorov complexity of Turing-hard sets, Dimension extractors and optimal decompression, Monotonous betting strategies in warped casinos, Constructive Dimension and Hausdorff Dimension: The Case of Exact Dimension, Learning hurdles for sleeping experts, Restriction access, Mechanism design with approximate valuations, Quantum strategic game theory, The curse of simultaneity, No justified complaints, From randomizing polynomials to parallel algorithms, Practical verified computation with streaming interactive proofs, Paging for multi-core shared caches, Noise vs computational intractability in dynamics, Distribution free evolvability of polynomial functions over all convex loss functions, Algorithms on evolving graphs, Towards deterministic tree code constructions, Linear time decoding of regular expander codes, List decoding subspace codes from insertions and deletions, Bounds on locally testable codes with unique tests, Approximately optimal mechanism design via differential privacy, Fairness through awareness, Dynamics of prisoner's dilemma and the evolution of cooperation on networks, Crowdsourced Bayesian auctions, Super-polynomial quantum speed-ups for boolean evaluation trees with hidden structure, Quantum interactive proofs with weak error bounds, Quantum money from knots, (Leveled) fully homomorphic encryption without bootstrapping, From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again, Targeted malleability, Sherali-Adams relaxations and indistinguishability in counting logics, Graph densification, Spectral sparsification via random spanners, Multicommodity flows and cuts in polymatroidal networks, On persistent homotopy, knotted complexes and the Alexander module, Gadgets and anti-gadgets leading to a complexity dichotomy, On beating the hybrid argument, Linear programming, width-1 CSPs, and robust satisfaction, Marginal hitting sets imply super-polynomial lower bounds for permanent, Mutual Dimension, Relative Kolmogorov complexity and geometry, Calibrating Randomness, Effective symbolic dynamics, random points, statistical behavior, complexity and entropy, On partial randomness, Finite state incompressible infinite sequences, Entropy rates and finite-state dimension, The Intersection of Algorithmically Random Closed Sets and Effective Dimension, Dimension spectra of lines1, Extending the reach of the point-to-set principle, Dimension and the structure of complexity classes, Unnamed Item, Fractal Intersections and Products via Algorithmic Dimension, On Oscillation-free ε-random Sequences, Connectivity Properties of Dimension Level Sets, A Characterization of Constructive Dimension, On the degree of univariate polynomials over the integers, Translating the Cantor set by a random real, Unnamed Item, High-confidence predictions under adversarial uncertainty, Quantum rejection sampling, Compressed matrix multiplication, INFINITE ITERATED FUNCTION SYSTEMS IN CANTOR SPACE AND THE HAUSDORFF MEASURE OF ω-POWER LANGUAGES, Unnamed Item, Randomness and Effective Dimension of Continued Fractions., Point Degree Spectra of Represented Spaces, Algorithmic Fractal Dimensions in Geometric Measure Theory

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Gales suffice for constructive dimension
• Incompleteness theorems for random reals
• Descriptive set theory
• Classical recursion theory. Vol. II
• Algorithmic approach to the prediction problem
• The complexity and effectiveness of prediction algorithms
• On Hausdorff and topological dimensions of the Kolmogorov complexity of the real line
• A tight upper bound on Kolmogorov complexity and uniformly optimal prediction
• Noiseless coding of combinatorial sources, Hausdorff dimension, and Kolmogorov complexity
• On the sum of digits of real numbers represented in the dyadic system. (On sets of fractional dimensions II.)
• A Kolmogorov complexity characterization of constructive Hausdorff dimension.
• Process complexity and effective random tests
• Kolmogorov complexity and Hausdorff dimension
• Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. (Randomness and probability. An algorithmic foundation of probability theory)
• On equivalence of infinite product measures
• Combinatorial foundations of information theory and the calculus of probabilities
• Von Mises' definition of random sequences reconsidered
• A Theory of Program Size Formally Identical to Information Theory
• Dimension in Complexity Classes
• A New Interpretation of the von Mises' Concept of Random Sequence
• On the Length of Programs for Computing Finite Binary Sequences
• On the Length of Programs for Computing Finite Binary Sequences
• The Kleene Hierarchy Classification of Recursively Random Sequences
• Complexity oscillations in infinite binary sequences
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• A unified approach to the definition of random sequences
• The definition of random sequences
• A formal theory of inductive inference. Part I
• THE FRACTIONAL DIMENSION OF A SET DEFINED BY DECIMAL PROPERTIES
• Note on arithmetic models for consistent formulae of the predicate calculus