On a complete set of operations for factorizing codes
It is known that the class of factorizing codes, i.e., codes satisfying the factorization conjecture formulated by Schützenberger, is closed under...
On a complete set of operations for factorizing codes
It is known that the class of factorizing codes, i.e., codes satisfying the factorization conjecture formulated by Schützenberger, is closed under two operations: the classical composition of codes and substitution of codes. A natural question which arises is whether a finite set O of operations exists such that each factorizing code can be obtained by using the operations in O and starting with prefix or suffix codes. O is named here a complete set of operations (for factorizing codes). We show...
On a test for codes.
On codes having no finite completion
On codes with finite interpreting delay : a defect theorem
On codes with finite interpreting delay: a defect theorem
We introduce two new classes of codes, namely adjacent codes and codes with finite interpreting delay. For each class, we establish an extension of the defect theorem.
On equivalence of two tests for codes.
On infinitary finite length codes
On minimal redundancy codes.
A code X over the alphabet A is complete if the submonoid X* generated by X meets all two-sided ideals of A*. If one measures the cost of a finite code X over A, with respect to a given information source S, by the quantity gamma(X) = <X> ln |A|, we say that X is completely optimal for S if it does not exist any code X', over an arbitrary alphabet, such that gamma (X') < gamma (X). One can show that for |X| ≤ 5 a completely optimal code has to be complete. However for |X| > 5 there exist uncomplete codes with the property of having a bounded synchronization delay and a redundancy which is minimal. From the information point of view these uncomplete codes should be preferred to the complete ones, which are such to have, except for the biprefix case, an infinite delay of deciphering in at least one direction. Moreover for some values of |X| complete biprefix codes do not exist.
On Simple Stochastic Models
On some subsemigroups of a free semigroup.
On the degree of finite maximal biprefix codes.
On the size of transducers for bidirectional decoding of prefix codes
In a previous paper [L. Giambruno and S. Mantaci, Theoret. Comput. Sci. 411 (2010) 1785–1792] a bideterministic transducer is defined for the bidirectional deciphering of words by the method introduced by Girod [IEEE Commun. Lett. 3 (1999) 245–247]. 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 decoding by this method is defined. It is proved also that this transducer...
On the size of transducers for bidirectional decoding of prefix codes
In a previous paper [L. Giambruno and S. Mantaci, Theoret. Comput. Sci. 411 (2010) 1785–1792] a bideterministic transducer is defined for the bidirectional deciphering of words by the method introduced by Girod [IEEE Commun. Lett. 3 (1999) 245–247]. 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 decoding 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 a 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. We moreover consider two special cases of codes: maximal uniform codes and a class of codes, that we name string-codes. We show that they represent, for maximal codes, the extreme cases with regard to the number of states in terms of different sizes. Moreover we prove that prefix codes corresponding to isomorphic trees have transducers that are isomorphic as unlabeled graphs.
On the size of transducers for bidirectional decoding of prefix codes
In a previous paper [L. Giambruno and S. Mantaci, Theoret. Comput. Sci. 411 (2010) 1785–1792] a bideterministic transducer is defined for the bidirectional deciphering of words by the method introduced by Girod [IEEE Commun. Lett. 3 (1999) 245–247]. 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 decoding by this...
On the structure of some group codes.