Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 6 / Issue 1

available in:   HTML (42 bytes) PDF (161 kB) PS (44 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-006-01-0130


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.