Not Every Domain of a Plain Decompressor Contains the Domain of a Prefix-Free One - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue Theoretical Computer Science Année : 2012

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

Mikhail Andreev
  • Fonction : Auteur
Ilya Razenshteyn
  • Fonction : Auteur
Alexander Shen
Systèmes complexes, automates et pavages

Résumé

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.

Domaines

Complexité [cs.CC] Théorie de l'information et codage [math.IT] Théorie de l'information [cs.IT] Logique [math.LO]

Andrei Romashchenko  : Connectez-vous pour contacter le contributeur

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00845800

Soumis le : mercredi 17 juillet 2013-18:00:26

Dernière modification le : lundi 22 avril 2024-17:14:26

Consulter le texte intégral

Dates et versions

lirmm-00845800 , version 1 (17-07-2013)

Identifiants

Citer

Mikhail Andreev, Ilya Razenshteyn, Alexander Shen. Not Every Domain of a Plain Decompressor Contains the Domain of a Prefix-Free One. Theoretical Computer Science, 2012, 412 (1-2), pp.482-486. ⟨10.1016/j.tcs.2010.10.012⟩. ⟨lirmm-00845800⟩

Exporter

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

CNRS ESCAPE LIRMM MIPS UNIV-MONTPELLIER
62 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More