UNIVERSAL CODING OF INTEGERS AND UNBOUNDED SEARCH-TREES

In this paper we study universal coding problems for the integers, in particular, establish rather tight lower and upper bounds for the Elia s omega code and other codes, In these bounds, the so-called log-star function plays a central role. Furthermore, we investigate unbounded s earch trees induced by these codes, including the Bentley-Yao search t ree, We will reveal beautiful recursion structures latent in these sea rch trees as well as in these codes. Finally, we introduce the modifie d log-star function to reveal the existance of better prefix codes tha n Elias omega code and other known codes.