×

Noncommutative factorization of variable-length codes. (English) Zbl 0629.68079

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 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.
Reviewer: H.Jürgensen

MSC:

68Q45 Formal languages and automata
94A45 Prefix, length-variable, comma-free codes
20M35 Semigroups in automata theory, linguistics, etc.

Citations:

Zbl 0149.026
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] J. Berstel and D. Perrin, The Theory of Codes (Academic Press, New York, to appear).; J. Berstel and D. Perrin, The Theory of Codes (Academic Press, New York, to appear). · Zbl 1022.94506
[2] Blanchard, F.; Perrin, D., Relévement d’une mesure ergodique par un codage, Z. Wahrscheinlichkeit., 54, 303-311 (1980) · Zbl 0441.60004
[3] Boë, J.-M., Sur les codes synchronisants coupants, (Proc. Colloquium Arco Felice. Proc. Colloquium Arco Felice, Naples (1981), C.N.R: C.N.R Roma), 7-10 · Zbl 0542.20046
[4] Boë, J.-M.; de Luca, A.; Restivo, A., Minimal complete sets of words, Theoret. Comput. Sci., 12, 325-332 (1980) · Zbl 0446.20036
[5] Césari, Y., Propriétés combinatoires des codes bipréfixes complets finis, (Perrin, D., Actes de la 7ème école de printemps d’informatique théorique (1979)), 29-46, Jougne
[6] Clifford, A. H.; Preston, G. B., (The Algebraic Theorey of Semigroups, Vol. 1 (1961), Amer. Math. Soc: Amer. Math. Soc Providence, RI)
[7] Cohn, P. M., Free associative algebras, Bull. London Math. Soc., 1-39 (1969) · Zbl 0174.32501
[8] Cohn, P. M., Free Rings and Their Relations (1971), Academic Press: Academic Press New York · Zbl 0232.16003
[9] Cohn, P. M., The universal field of fractions of a semifir, I: Numerators and denominators, (Proc. London Math. Soc., 44 (1982)), 1-32, (3) · Zbl 0424.16002
[10] De Felice, C., On the triangle conjecture, Inform. Process. Lett., 14, 197-200 (1982) · Zbl 0487.68074
[11] Eilenberg, S., (Automata, Languages and Machines, Vol. A (1974), Academic Press: Academic Press New York) · Zbl 0317.94045
[12] Hansel, G., Baïonnettes et cardinaux, Discrete Math., 39, 331-335 (1982) · Zbl 0486.20032
[13] Hansel, G.; Perrin, D., Codes and Bernoulli partitions, Math. System Theory, 16, 133-157 (1983) · Zbl 0519.94012
[14] Hansel, G.; Perrin, D.; Reutenauer, C., Factorizing the polynomial of a code, Trans. Amer. Math. Soc., 285, 91-105 (1984) · Zbl 0556.20049
[15] Lallement, G., Semigroups and Combinatorial Applications (1979), Wiley: Wiley New York · Zbl 0421.20025
[16] Lyndon, R. C.; Schupp, P., Combinatorial Group Theory (1977), Springer: Springer Berlin · Zbl 0368.20023
[17] Mauceri, S.; Restivo, A., A family of codes commutatively equivalent to prefix codes, Inform. Process. Lett., 12, 1-4 (1981) · Zbl 0466.94024
[18] Perrin, D., Codes asynchrones, Bull. Soc. Math. France, 105, 385-404 (1977) · Zbl 0391.94017
[19] Perrin, D.; Schützenberger, M. P., un problème élémentaire de la théorie de l’information, (Colloques Internationaux du CNRS, No. 276. Colloques Internationaux du CNRS, No. 276, Cachan (1977)) · Zbl 0483.94028
[20] Perrin, D.; Schützenberger, M. P., A conjecture on sets of different of integer pairs, J. Combin. Theory (B), 30, 91-93 (1981) · Zbl 0468.05033
[21] J.-E. Pin and I. Simon, A note on the triangle conjecture, J. Combin. Theory (A) 32 106-109.; J.-E. Pin and I. Simon, A note on the triangle conjecture, J. Combin. Theory (A) 32 106-109.
[22] Restivo, A., On codes having no finite completions, Discrete Math., 17, 309-331 (1977) · Zbl 0357.94011
[23] Reutenauer, C., Sur un théorème de Schützenberger, Notes Comptes Rendus Acad. Sci. Paris, 296, 619-621 (1983) · Zbl 0527.68052
[24] Reutenauer, C., Sulla fattorizzazione dei codici, Ricerche di Matematica, 32, 115-130 (1983) · Zbl 0543.68063
[25] Schützenberger, M. P., Sur certains sous-monoïdes libres, Bull. Soc. Math. France, 93, 209-223 (1965) · Zbl 0149.02601
[26] Shor, P., J. Combin. Theory (A), 38, 110-112 (1985) · Zbl 0558.20032
[27] Vincent, M., Une famille de codes indécomposables, (Thèse 3ème cycle (1982), Univ. Sci. Techniques Languedoc: Univ. Sci. Techniques Languedoc Montpellier) · Zbl 0402.94036
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.