Information Distance Revisited - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Preprints, Working Papers, ... Year : 2020

Information Distance Revisited


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
Origin Files produced by the author(s)

Dates and versions

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



Bruno Bauwens, Alexander Shen. Information Distance Revisited. 2020. ⟨lirmm-01982345⟩
105 View
63 Download



Gmail Mastodon Facebook X LinkedIn More