Generalizing the Kraft-McMillan Inequality to Restricted Languages
Mordecai Golin
HKUST

Date: Friday September 10, 2004
Time 11-12
Venue: Room 3464 


Abstract
Given a fixed alphabet, a "prefix-code" is a set of words
built from the alphabet such that no word in the set is a
 prefix of any other word in the set.

The "Level-Sequence" of a code is a sequence of non-negative
integers, in which the i'th integer is the number of words
of length i in the code.


The Kraft-Inequality provides a necessary and sufficient 
condition for determining whether a given sequence of
non-negative integers is the level-sequence of some prefix-code.


In this talk  we examine how the Kraft-Inequality condition 
changes when the code in not only required to be prefix 
but all of the codewords are  restricted to belong to a given 
specific language.  For example, the restriction language
might be all words that end in a particular pattern,
or (if the alphabet is binary)  might be all words in 
which the number of zeros equals the number of ones.


This is joint work with Hyeon-Suk Na