Skip to Main content Skip to Navigation
Journal articles

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.
Complete list of metadata

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00845800
Contributor : Andrei Romashchenko <>
Submitted on : Wednesday, July 17, 2013 - 6:00:26 PM
Last modification on : Friday, May 21, 2021 - 8:22:02 PM

Links full text

Identifiers

  • 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⟩

Share

Metrics

Record views

161