JUCS - Journal of Universal Computer Science 6(1): 130-135, doi: 10.3217/jucs-006-01-0130
Free-Extendible Prefix-Free Sets and an Extension of the Kraft-Chaitin Theorem
expand article infoCristian Grozea‡
‡ Faculty of Mathematics Bucharest University, Bucharest, Romania

Corresponding author: Cristian Grozea ( chrisg@phobos.cs.unibuc.ro )

© Cristian Grozea.
This article is freely available under the J.UCS Open Content License.
Citation: Grozea C (2000) Free-Extendible Prefix-Free Sets and an Extension of the Kraft-Chaitin Theorem. JUCS - Journal of Universal Computer Science 6(1): 130-135. https://doi.org/10.3217/jucs-006-01-0130
Open Access
Abstract
First, the dual set of a finite prefix-free set is defined. Using this notion we describe equivalent conditions for a finite prefix-free set to be indefinitely extendible. This lead to a simple proof for the Kraft-Chaitin Theorem. Finally, we discuss the influence of the alphabet size on the indefinite extensibility property. 1 C.S.Calude and G.Stefanescu (eds.). Automata, Logic, and Computability. Special issue dedicated to Professor Sergiu Rudeanu Festschrift.
Keywords
Prefix-free set, Kraft's inequality