Construction of a family of finite maximal codes. (English) Zbl 0664.94022

STACS 88, Theoretical aspects of computer science, Proc. 5th Annu. Symp., Bordeaux/France 1988, Lect. Notes Comput. Sci. 294, 159-169 (1988).
[For the entire collection see Zbl 0635.00015.]
The author gives an algorithm to construct all variable-length codes C which are maximal, finite and have a factorization of the form \(C-1=P(A- 1)S\) in the algebra of noncommutative polynomials over the alphabet A, with P a polynomial in the single letter a. The algorithm depends on the solution of an inequality of the form \(a^{M+I}\leq a^{M+I+1}+a^ I,\) where I satisfies \(I+J=\{0,1,...,n-1\}\), i.e. each x in this interval is a unique sum \(i+j\) with \(i\in I\), \(j\in J\). Calculations of such I, J have been made by Krasner-Ranulac and are related to the factorization of cyclic groups.
Reviewer: C.Reutenauer


94A45 Prefix, length-variable, comma-free codes


Zbl 0635.00015