Nonapproximability of the normalized information distance

DOI10.1016/J.JCSS.2010.06.018MaRDI QIDQ716306zbMATH OpenOpenAlexWikidataFDO

Authors Sebastiaan A. Terwijn, Leen Torenvliet, Paul M. B. Vitányi

Publication date 28 April 2011

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://ir.cwi.nl/pub/19043

zbMATH Keywords

Kolmogorov complexitynormalized information distancesemicomputability

Mathematics Subject Classification ID

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

Recommendations

• Common pitfalls using the normalized compression distance: what to watch out for in a compressor
• A safe approximation for Kolmogorov complexity
• Normalized Information Distance
• Normalized information distance and the oscillation hierarchy
• INFORMATION DISTANCE AND ITS APPLICATIONS

Cites work

• scientific article; zbMATH DE number 3427210 (Why is no real title available?)
• An introduction to Kolmogorov complexity and its applications
• Clustering by Compression
• Independent minimum length programs to translate between given strings
• Information distance
• Information distance and conditional complexities
• Logical operations and Kolmogorov complexity
• Notes on sum-tests and independence tests
• Systems of strings with high mutual complexity
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• The Similarity Metric
• Upper semi-lattice of binary strings with the relation ``\(x\) is simple conditional to \(y\)

Cited in

(10)

• Evaluating the Impact of Information Distortion on Normalized Compression Distance
• The Normalized Algorithmic Information Distance Can Not Be Approximated
• Compression-based distance between string data and its application to literary work classification based on authorship
• A safe approximation for Kolmogorov complexity
• Normalized Information Distance
• Applying a normalized compression metric to the measurement of dialect distance
• Normalized information distance and the oscillation hierarchy
• Similarity and denoising
• Preliminary results on masquerader detection using compression based similarity metrics
• The Normalized Compression Distance Is Resistant to Noise

This page was built for publication: Nonapproximability of the normalized information distance

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