|
Free-Extendible Prefix-Free Sets and an Extension of the Kraft-Chaitin Theorem
Cristian Grozea (Faculty of Mathematics Bucharest University, Romania)
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: Kraft's inequality, Prefix-free set
Categories: F.2.2, H.
|
