zbMATH — the first resource for mathematics

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

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