Not Every Domain of a Plain Decompressor Contains the Domain of a Prefix-Free One

Mikhail Andreev Ilya Razenshteyn Alexander Shen 1
1 ESCAPE - Systèmes complexes, automates et pavages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : C.Calude, A.Nies, L.Staiger, and F.Stephan posed the following question about the relation between plain and prefix Kolmogorov complexities (see their paper in DLT 2008 conference proceedings): does the domain of every optimal decompressor contain the domain of some optimal prefix-free decompressor? In this paper we provide a negative answer to this question.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2012, 412 (1-2), pp.482-486
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00845800
Contributeur : Andrei Romashchenko <>
Soumis le : mercredi 17 juillet 2013 - 18:00:26
Dernière modification le : jeudi 24 mai 2018 - 15:59:23

Lien texte intégral

Identifiants

  • HAL Id : lirmm-00845800, version 1
  • ARXIV : 1001.4462

Collections

Citation

Mikhail Andreev, Ilya Razenshteyn, Alexander Shen. Not Every Domain of a Plain Decompressor Contains the Domain of a Prefix-Free One. Theoretical Computer Science, Elsevier, 2012, 412 (1-2), pp.482-486. 〈lirmm-00845800〉

Partager

Métriques

Consultations de la notice

76