Information measures for infinite sequences

DOI10.1016/j.tcs.2010.03.026zbMath1207.68171OpenAlexW2134836373WikidataQ62038782 ScholiaQ62038782MaRDI QIDQ974755

Luís Antunes, André Souto

Publication date: 7 June 2010

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: http://repositorio.inesctec.pt/handle/123456789/2960

zbMATH Keywords

Kolmogorov complexitycomputational depthsophistication

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Low-depth witnesses are easy to find
• Depth as randomness deficiency
• Sophistication revisited
• Entropy, Hausdorff measures old and new, and limit sets of geometrically finite Kleinian groups
• A Kolmogorov complexity characterization of constructive Hausdorff dimension.
• The Kolmogorov complexity of random reals
• Computational depth: Concept and applications
• Asymptotic orbit complexity of infinite measure preserving transformations
• An almost machine-independent theory of program-length complexity, sophistication, and induction
• Effective Strong Dimension in Algorithmic Information and Computational Complexity
• Two definitions of fractional dimension
• Dimension in Complexity Classes
• Algorithmic statistics
• Algorithmic Complexity and Stochastic Properties of Finite Binary Sequences
• On the Length of Programs for Computing Finite Binary Sequences
• Complexity oscillations in infinite binary sequences
• A formal theory of inductive inference. Part I
• An introduction to Kolmogorov complexity and its applications