Compressibility and uniform complexity

DOI10.1016/S0020-0190(97)00070-7zbMATHOpenAlexMaRDI QIDQ287086FDO

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

computational complexityKolmogorov complexitycompressibilitymulti-tape Turing machineuniform complexity

Mathematics Subject Classification ID

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

Recommendations

• Publication:4348124
• Kobayashi compressibility
• Time-bounded incompressibility of compressible strings and sequences
• Compressibility and resource bounded measure
• Publication:4023359

Cites work

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

Cited in

(13)

• Compression and hadamard power inequalities
• Compressibility of Deterministic and Random Infinite Sequences
• Inequalities and algorithms for universal data compression
• 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 and resource bounded measure
• On compressing complete designs
• A theory of incremental compression
• Unconditional bases and bit-level compression
• Compressibility and resource bounded measure
• Kobayashi compressibility
• Compression and diffusion: a joint approach to detect complexity.
• 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)