Noncommutative factorization of variable-length codes (Q1094145)

Let A be a finite alphabet, let \(C\subseteq A^*\) be a code and at the same time the characteristic formal power series with integer coefficients, and let \(\rho\) be the canonical homomorphism of the semiring of formal power series with non-commutative unknowns in A into the semiring of formal power series with commutative unknowns in A (with integer coefficients in either case). A result of \textit{M. P. Schützenberger} [Bull. Soc. Math. France 93, 209-223 (1965; Zbl 0149.026)] says that a finite maximal code C has a factorization into polynomials of the form \[ \rho (C)-1=PS(\rho (A)- 1)(d+(\rho (A)-1)Q), \] where \(S=1\) if and only if C is a prefix code, \(P=1\) if and only if C is a suffix code, and d is the degree of C. The main result of this paper is a non-commutative version of this factorization, that is, \[ C-1=P(d(A-1)+(A-1)Q(A-1))S \] with the same conditions on C, P, S, and d. The result is then applied to answer several long-standing open questions.