Nonapproximability of the normalized information distance
From MaRDI portal
Publication:716306
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
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)