×

On some Schützenberger conjectures. (English) Zbl 1007.68097

Summary: In this paper we consider factorizing codes \(C\) over \(A\), i.e., codes verifying the factorization conjecture by Schützenberger. Let \(n\) be the positive integer such that \(a^n\in C\), we show how we can construct \(C\) starting with factorizing codes \(C'\) with \(a^{n'}\in C'\) and \(n' < n\), under the hypothesis that all words \(a^iza^j\) in \(C\), with \(z\in(A\setminus a)A^*(A\setminus a)\cup (A\setminus a)\), satisfy \(i, j,>n\). The operation involved, already introduced by Anselmo, is also used to show that all maximal codes \(C=P(A-1)S+1\) with \(P, S\in {\mathbf Z}\langle A\rangle\) and \(P\) or \(S\) in \({\mathbf Z}\langle a\rangle\) can be constructed by means of this operation starting with prefix and suffix codes. Old conjectures by Schützenberger have been revised.

MSC:

68Q45 Formal languages and automata
68Q70 Algebraic theory of languages and automata
94A60 Cryptography
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Anselmo, M.2000, A non-ambiguous decomposition of regular languages and factorizing codes, submitted for publication. [Extended abstract in “Preproc. DLT”99”, Aachener Informatik-Berichte Vol. 99-51999, 103-115]; Anselmo, M.2000, A non-ambiguous decomposition of regular languages and factorizing codes, submitted for publication. [Extended abstract in “Preproc. DLT”99”, Aachener Informatik-Berichte Vol. 99-51999, 103-115]
[2] Anselmo, M.; Restivo, A., On languages factorizing the free monoid, Int. J. Algebra Comput., 4, 413-427 (1996) · Zbl 0859.68052
[3] Berstel, J.; Perrin, D., Theory of Codes (1985), Academic Press: Academic Press New York · Zbl 1022.94506
[4] Berstel, J.; Reutenauer, C., Rational series and their languages, EATCS Monogr. Theoret. Comput. Sci., 12 (1988) · Zbl 0668.68005
[5] Boë, J. M., Sur les codes factorisants, (Perrin, D., Théorie des codes (1979)), 1-8
[6] Bruyère, V.; De Felice, C., Synchronization and decomposability for a family of codes, Int. J. Algebra Comput., 4, 367-393 (1992) · Zbl 0763.94004
[7] Bruyère, V.; Latteux, M., Variable-Length Maximal Codes (1996), Springer-Verlag: Springer-Verlag Berlin/New York, p. 24-47 · Zbl 1046.94511
[8] De Felice, C. 1984, Construction et complétion de codes finis, Thèse de 3ème cycle, Université de Paris VII. [Rapport LITP 85-3, 1985, ]; De Felice, C. 1984, Construction et complétion de codes finis, Thèse de 3ème cycle, Université de Paris VII. [Rapport LITP 85-3, 1985, ]
[9] De Felice, C., Construction of a family of finite maximal codes, Theoret. Comput. Sci., 63, 157-184 (1989) · Zbl 0667.68079
[10] De Felice, C., A partial result about the factorization conjecture for finite variable-length codes, Discrete Math., 122, 137-152 (1993) · Zbl 0798.68084
[11] De Felice, C., On a property of the factorizing codes, Int. J. Algebra Comput., 9, 325-345 (1999) · Zbl 1040.68051
[12] De Felice, C., Hajós factorizations of cyclic groups-A simpler proof of a characterization, J. Automat. Lang. Combin., 4, 111-116 (1999) · Zbl 0953.94016
[13] De Felice, C.2000, Factorizing codes and Schützenberger conjectures, in; De Felice, C.2000, Factorizing codes and Schützenberger conjectures, in · Zbl 0996.68087
[14] De Felice, C.; Reutenauer, C., Solution partielle de la conjecture de factorisation des codes, Comptes Rendus Acad. Sci. Paris, 302, 169-170 (1986) · Zbl 0616.68066
[15] Hajós, G., Sur la factorisation des groupes abéliens, Casopis Pest. Mat. Fys., 74, 157-162 (1950) · Zbl 0039.01901
[16] Krasner, M.; Ranulac, B., Sur une propriété des polynômes de la division du cercle, C. R. Acad. Sci. Paris, 240, 397-399 (1937) · JFM 63.0044.03
[17] Lam, N. H., Hajós factorizations and completion of codes, Theoret. Comput. Sci., 182, 245-256 (1997) · Zbl 1053.20531
[18] Perrin, D.; Schützenberger, M. P., Un problème élémentaire de la théorie de l’information, Colloq. Int. CNRS, 276, 249-260 (1977)
[19] Perrin, D.; Schützenberger, M. P., A conjecture on sets of differences of integer pairs, J. Combin. Theory Ser. B, 30, 91-93 (1981) · Zbl 0468.05033
[20] Restivo, A., On codes having no finite completions, Discrete Math., 17, 309-316 (1977) · Zbl 0357.94011
[21] Reutenauer, C., Sulla fattorizzazione dei codici, Ricerche di Mat., 32, 115-130 (1983) · Zbl 0543.68063
[22] Reutenauer, C., Non commutative factorization of variable-length codes, J. Pure Appl. Algebra, 36, 167-186 (1985)
[23] Schützenberger, M. P. 1955, Une théorie algébrique du codage, Séminaire Dubreil-Pisot 1955-56, exposé No. 15.; Schützenberger, M. P. 1955, Une théorie algébrique du codage, Séminaire Dubreil-Pisot 1955-56, exposé No. 15.
[24] Zhang, L.; Gu, C. K., Two classes of factorizing codes-(p, p)-codes and (4, 4)-codes, (Ito, M.; Jürgensen, H., Words, Languages and Combinatorics II (1994), World Scientific: World Scientific Singapore), 477-483 · Zbl 0873.94011
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.