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

Mikhail Andreev; Ilya Razenshteyn; Alexander Shen

doi:10.1016/j.tcs.2010.10.012

Journal Articles Theoretical Computer Science Year : 2012

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

, , (1)

Mikhail Andreev

Function : Author

Ilya Razenshteyn

Function : Author

Alexander Shen

Function : Author
PersonId : 12768
IdHAL : alexander-shen
ORCID : 0000-0001-8605-7734
IdRef : 074188569

Systèmes complexes, automates et pavages

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.

Domains

Computational Complexity [cs.CC] Information Theory [math.IT] Information Theory [cs.IT] Logic [math.LO]

Andrei Romashchenko : Connect in order to contact the contributor

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

Submitted on : Wednesday, July 17, 2013-6:00:26 PM

Last modification on : Tuesday, September 3, 2024-1:56:20 PM

Dates and versions

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

Identifiers

HAL Id : lirmm-00845800 , version 1
ARXIV : 1001.4462
DOI : 10.1016/j.tcs.2010.10.012

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⟩

Export

BibTeX XML-TEI Dublin Core DC Terms EndNote DataCite

Collections

CNRS ESCAPE LIRMM MIPS UNIV-MONTPELLIER

63 View

0 Download

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

Abstract

Domains

Dates and versions

Identifiers

Cite

Export

Collections

Altmetric

Share