Information Distance Revisited - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2020

Information Distance Revisited

Résumé

We consider the notion of information distance between two objects x and y introduced by Bennett, G\'acs, Li, Vitanyi, and Zurek [1] as the minimal length of a program that computes x from y as well as computing y from x, and study different versions of this notion. It was claimed by Mahmud [11] that the prefix version of information distance equals max(K(x|y), K(y|) + O(1) (this equality with logarithmic precision was one of the main results of the paper by Bennett, G\'acs, Li, Vitanyi, and Zurek). We show that this claim is false.
Fichier principal
Vignette du fichier
1807.11087.pdf (339.38 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-01982345 , version 1 (17-01-2020)

Identifiants

Citer

Bruno Bauwens, Alexander Shen. Information Distance Revisited. 2020. ⟨lirmm-01982345⟩
105 Consultations
63 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More