Kraft-Chaitin Inequality Revisited

Calude, C; Grozea, C

dc.contributor.author	Calude, C	en
dc.contributor.author	Grozea, C	en
dc.date.accessioned	2009-04-16T23:10:28Z	en
dc.date.available	2009-04-16T23:10:28Z	en
dc.date.issued	1996-04	en
dc.identifier.citation	CDMTCS Research Reports CDMTCS-013 (1996)	en
dc.identifier.issn	1178-3540	en
dc.identifier.uri	http://hdl.handle.net/2292/3522	en
dc.description.abstract	Kraft's inequality [9] is essential for the classical theory of noiseless coding [1, 8]. In algorithmic information theory [5, 7, 2] one needs an extension of Kraft's condition from finite sets to (infinite) recursively enumerable sets. This extension, known as Kraft-Chaitin Theorem, was obtained by Chaitin in his seminal paper [4] (see also, [3, 2], [10]). The aim of this note is to offer a simpler proof of Kraft-Chaitin Theorem based on a new construction of the prefix-free code.	en
dc.publisher	Department of Computer Science, The University of Auckland, New Zealand	en
dc.relation.ispartofseries	CDMTCS Research Report Series	en
dc.rights.uri	https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm	en
dc.source.uri	http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial	en
dc.title	Kraft-Chaitin Inequality Revisited	en
dc.type	Technical Report	en
dc.subject.marsden	Fields of Research::280000 Information, Computing and Communication Sciences	en
dc.rights.holder	The author(s)	en
dc.rights.accessrights	http://purl.org/eprint/accessRights/OpenAccess	en