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 Access content directly
Journal Articles Theoretical Computer Science Year : 2012

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

Mikhail Andreev
  • Function : Author
Ilya Razenshteyn
  • Function : Author
Alexander Shen

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.

Dates and versions

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

Identifiers

Cite

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⟩
63 View
0 Download

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More