Characterization Results for Time-Varying Codes

Article type: Research Article

Authors: Ţiplea, Ferucio | Mäkinen, Erkki | Trincă, Dragos | Enea, Costel

Affiliations: Faculty of Computer Science, ``Al.I.Cuza'' University of Iaşi, 6600 Iaşi, Romania | Department of Computer and Information Sciences, P.O. Box 607, FIN-33014 University of Tampere, Finland

Abstract: Time-varying codes associate variable length code words to letters being encoded depending on their positions in the input string. These codes have been introduced in [8] as a proper extension of L codes. This paper is devoted to a further study of time-varying codes. First, we show that adaptive Huffman encodings are special cases of encodings by time-varying codes. Then, we focus on three kinds of characterization results: characterization results based on decompositions over families of sets of words, a Schützenberger like criterion, and a Sardinas-Patterson like characterization theorem. All of them extend the corresponding characterization results known for classical variable length codes.

Keywords:

Journal: Fundamenta Informaticae, vol. 53, no. 2, pp. 185-198, 2002