Not Every Domain of a Plain Decompressor Contains the Domain of a Prefix-Free One
classification
💻 cs.IT
cs.CCmath.ITmath.LO
keywords
domaindecompressoreveryoptimalplainprefix-freequestionanswer
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.