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 (only showing first 100 items - show all)

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

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

This page was built for publication: The dimensions of individual strings and sequences