Noncommutative factorization of variable-length codes
type: Item
instance of: scholarly article
title: Noncommutative factorization of variable-length codes
zbMATH Open document ID: 0629.68079
DOI: 10.1016/0022-4049(85)90069-6
author: Christophe Reutenauer
published in: Journal of Pure and Applied Algebra
publication date: 1985-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 94A45
Mathematics Subject Classification ID: 20M35
zbMATH DE Number: 4024820
zbMATH Keywords: factorization of variable-length codes
zbMATH Keywords: complete characterization of maximal and finite codes
zbMATH Keywords: invariance property
zbMATH Keywords: characteristic formal power series
MaRDI profile type: Publication
full work available at URL: 0022-4049(85)90069-6
OpenAlex ID: W2090538719
cites work: Q4430300
cites work: Rel�vement d'une mesure ergodique par un codage
cites work: Q3329658
cites work: Minimal complete sets of words
cites work: Q3848243
cites work: Free Associative Algebras
cites work: Q5639812
cites work: The Universal Field of Fractions of a Semifir I. Numerators and Denominators
cites work: On the triangle conjecture
cites work: Q4079524
cites work: Baionnettes et cardinaux
cites work: Codes and Bernoulli partitions
cites work: Factorizing The Polynomial of a Code
cites work: Q3853827
cites work: Q4145882
cites work: A family of codes commutatively equivalent to prefix codes
cites work: Codes asynchrones
cites work: Q3942894
cites work: A conjecture on sets of differences of integer pairs
cites work: A note on the triangle conjecture
cites work: On codes having no finite completions
cites work: Q3042419
cites work: On the factorization of codes
cites work: Sur certains sous-monoïdes libres
cites work: A counterexample to the triangle conjecture
cites work: Une famille remarquable de codes indecomposables
description: scientific article; zbMATH DE number 4024820