On the factorization of codes (Q796308): Difference between revisions
From MaRDI portal
Removed claim: author (P16): Item:Q213124 |
Changed an Item |
||
Property / author | |||
Property / author: Christophe Reutenauer / rank | |||
Normal rank |
Revision as of 00:52, 11 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the factorization of codes |
scientific article |
Statements
On the factorization of codes (English)
0 references
1983
0 references
A code is a free subset of a free monoid. We show that a subset \(C\) of the free monoid \(X^*\) on the finite alphabet \(X\) is a finite and maximal code if and only if its characteristic polynomial \(\mathcal C\), element of the free associative algebra \(\mathbb Z<X>\) on \(X\), verifies \(\mathcal C-1=P(X-1)S\) for some polynomials \(P, S\) in \(\mathbb Z<X>\). This gives a partial answer to the factorization conjecture of Schützenberger \((P, S\) should moreover have nonnegative coefficients). A stronger result, which is the noncommutative version of \textit{M. P. Schützenberger}'s factorization theorem [Bull. Soc. Math. Fr. 93, 203--223 (1965; Zbl 0149.02601)], is to appear in [J. Pure Appl. Algebra 36, 167--185 (1985; Zbl 0629.68079)].
0 references
free subset of a free monoid
0 references
maximal code
0 references
characteristic polynomial
0 references
free associative algebra
0 references
factorization
0 references