Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Information Distance Revisited

Bruno Bauwens 1 Alexander Shen 2
2 ESCAPE - Systèmes complexes, automates et pavages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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.
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01982345
Contributor : Alexander Shen <>
Submitted on : Friday, January 17, 2020 - 1:34:50 PM
Last modification on : Friday, January 17, 2020 - 1:36:00 PM

File

1807.11087.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-01982345, version 1
  • ARXIV : 1807.11087

Citation

Bruno Bauwens, Alexander Shen. Information Distance Revisited. 2020. ⟨lirmm-01982345⟩

Share

Metrics

Record views

103

Files downloads

12