Theoretical Informatics and Applications Will be set by the publisher Informatique Théorique et Applications ON THE SIZE OF TRANSDUCERS FOR BIDIRECTIONAL DECODING OF PREFIX CODES

Abstract. In a previous paper [5] a bi-deterministic transducer is defined for the bidirectional decyphering of words by the method in-troduced by Girod [6]. Such a method is defined using prefix codes. Moreover a coding method, inspired by the Girod’s one, is introduced, and a transducer that allows both right-to-left and left-to-right decod-ing by this method is defined. It is proved also that this transducer is minimal. Here we consider the number of states of such a transducer, related to some features of the considered prefix code X. We find some bounds of such number of states in relation with different notions of “size ” of X. In particular, we give an exact formula for the number of states of transducers associated to maximal prefix codes, and we consider two special cases of maximal uniform codes and a class of codes, that we named string-codes, showing that they represent, for maximal codes, the extremal cases to this number of states in terms of different sizes. This fact formalizes somehow the intuition that for maximal prefix codes the farthest a code is from being uniform the greatest the number of states is in the correspondent transducer, respect to the different sizes of the code. Moreover we prove that prefix codes corresponding to isomorphic trees have transducers that are isomorphic as unlabeled graphs. 1991 Mathematics Subject Classification. 94B35, 68P30, 94A45. 1