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

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

Andreev, M. ; Razenshteyn, I. ; Shen, A.
Identifier: http://hdl.handle.net/2292/10529
Issue Date: 2010
Reference: CDMTCS Research Reports CDMTCS-376 (2010)
Rights: The author(s)
Rights (URI): https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm

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.

Show full item record

Files in this item

Icon
Size: 795.0Kb
Format: PDF
Icon
Related URL: http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Find Full text

This item appears in the following Collection(s)

Share

Search ResearchSpace


Browse

Statistics