Nonapproximability of the normalized information distance

DOI10.1016/J.JCSS.2010.06.018zbMATH Open1215.68116OpenAlexW2099666487WikidataQ60362747 ScholiaQ60362747MaRDI QIDQ716306FDOQ716306

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

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

zbMATH Keywords

Kolmogorov complexitynormalized information distancesemicomputability

Mathematics Subject Classification ID

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

Cites Work

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

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)