Compressibility and uniform complexity

DOI10.1016/S0020-0190(97)00070-7MaRDI QIDQ287086zbMATH OpenOpenAlexFDO

Authors M. Hermo

Publication date 26 May 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0020-0190(97)00070-7

zbMATH Keywords

compressibilitycomputational complexityKolmogorov complexitymulti-tape Turing machineuniform complexity

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1048038
• Kobayashi compressibility
• Time-bounded incompressibility of compressible strings and sequences
• Compressibility and resource bounded measure
• scientific article; zbMATH DE number 107775

Cites work

• A variant of the Kolmogorov concept of complexity
• An introduction to Kolmogorov complexity and its applications
• scientific article; zbMATH DE number 1048038 (Why is no real title available?)
• On the notion of infinite pseudorandom sequences

Cited in

(14)

• On compressing complete designs
• Inequalities and algorithms for universal data compression
• Compression and diffusion: a joint approach to detect complexity.
• A theory of incremental compression
• Unconditional bases and bit-level compression
• Compressibility and resource bounded measure
• Compression and hadamard power inequalities
• scientific article; zbMATH DE number 1048038 (Why is no real title available?)
• scientific article; zbMATH DE number 1998343 (Why is no real title available?)
• scientific article; zbMATH DE number 1774977 (Why is no real title available?)
• Compressibility of Deterministic and Random Infinite Sequences
• Compressibility and resource bounded measure
• Kobayashi compressibility
• Time-bounded incompressibility of compressible strings and sequences

This page was built for publication: Compressibility and uniform complexity

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