Compressibility and uniform complexity

DOI10.1016/S0020-0190(97)00070-7zbMATH Open1337.68141OpenAlexW2007616727MaRDI QIDQ287086FDOQ287086

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

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

zbMATH Keywords

computational complexityKolmogorov complexitycompressibilitymulti-tape Turing machineuniform complexity

Mathematics Subject Classification ID

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

Cites Work

• An introduction to Kolmogorov complexity and its applications
• On the notion of infinite pseudorandom sequences
• Title not available (Why is that?)
• A variant of the Kolmogorov concept of complexity

Cited In (13)

• Inequalities and algorithms for universal data compression
• Unconditional bases and bit-level compression
• Compression and diffusion: a joint approach to detect complexity.
• Title not available (Why is that?)
• Time-bounded incompressibility of compressible strings and sequences
• A theory of incremental compression
• On compressing complete designs
• Compressibility of Deterministic and Random Infinite Sequences
• Compression and hadamard power inequalities
• Title not available (Why is that?)
• Compressibility and resource bounded measure
• Compressibility and resource bounded measure
• Kobayashi compressibility

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)