×

Synchronization and decomposability for a family of codes. II. (English) Zbl 0842.94009

The main result is that, for any variable length code \(C\) on a two letter alphabet \(\{a, b\}\), such that \(C\) is maximal and finite and has at most 3 occurrences of \(b\) in each of its elements, \(C\) has always one or two factorizations; if \(C\) has degree 1, it has one factorization; if \(C\) has degree 2 or 3 it has two factorizations and they may be deduced from the precise form of \(C\) given by the authors, which is related to Krasner factorizations.

MSC:

94A45 Prefix, length-variable, comma-free codes
68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Berstel, J.; Perrin, D., Theory of Codes (1985), Academic Press: Academic Press New York · Zbl 1022.94506
[2] Berstel, J.; Reutenauer, C., Rational Series and their Languages, (EATCS Monographs, Vol. 12 (1988), Springer: Springer Berlin) · Zbl 0573.68037
[3] Boë, J. M., Une famille remarquable de codes indécomposables, (Lecture Notes in Comput. Sci., Vol. 62 (1978), Springer: Springer Berlin), 105-112 · Zbl 0402.94036
[4] Bruyère, V., Codes, (Thesis (1991), Université de Mons-Hainaut)
[5] Bruyère, V.; De Felice, C., Degree and decomposability of variable-length codes, (Proc. ICALP’ 91. Proc. ICALP’ 91, Lecture Notes in Comput. Sci., Vol. 510 (1991), Springer: Springer Berlin), 575-587 · Zbl 0766.68071
[6] Bruyère, V.; De Felice, C., Synchronization and decomposability for a family of codes, Internat. J. Algebra Comput., 2, 367-393 (1992) · Zbl 0763.94004
[7] Césari, Y., Sur l’application du théorème de Suschkevitch à l’étude des codes rationnels complets, (Lecture Notes in Comput. Sci. (1974), Springer: Springer Berlin), 342-350
[8] Cohn, P. M., On a generalization of the Euclidean algorithm, (Proc. Cambridge Philos. Soc., 57 (1961)), 18-30 · Zbl 0098.03202
[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., On the factorization conjecture, (Proc. STACS ’92. Proc. STACS ’92, Lecture Notes in Comput Sci., Vol. 577 (1992), Springer: Springer Berlin), 545-556 · Zbl 1494.68134
[11] De Felice, C., On the factorizations of cyclic groups (1992), manuscript
[12] De Felice, C.; Reutenauer, C., Solution partielle de la conjecture de factorisation des codes, C.R. Acad. Sci. Paris, 302, 169-170 (1986) · Zbl 0616.68066
[13] Fuchs, L., Abelian Groups (1960), Pergamon Press: Pergamon Press Oxford · Zbl 0100.02803
[14] Hajos, G., Sur le problème de factorisation des groupes cycliques, Acta Math. Acad. Sc. Hungar., 1, 189-195 (1950) · Zbl 0041.15702
[15] 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
[16] Nivat, M., Eléments de la théorie des codes, (Caianiello, E., Automata Theory (1966), Academic Press: Academic Press New York), 278-294 · Zbl 0208.45101
[17] Perrin, D., Codes asynchrones, Bull. Soc. Math. France, 105, 385-404 (1977) · Zbl 0391.94017
[18] Perrin, D.; Schützenberger, M. P., Un problème élémentaire de la théorie de l’information, (Théorie de l’Information. Théorie de l’Information, Colloques Internat. CNRS 276, Cachan (1977)), 249-260
[19] Restivo, A., On codes having no finite completions, Discrete Math., 17, 309-316 (1977) · Zbl 0357.94011
[20] Reutenauer, C., Noncommutative factorization of variable-length codes, J. Pure Appl. Algebra, 36, 167-186 (1985) · Zbl 0629.68079
[21] Schützenberger, M. P., Une theorie algébrique du codage, (Séminaire Dubreil-Pisot 1955-1956. Séminaire Dubreil-Pisot 1955-1956, exposé \(n^o 15 (1955))\) · Zbl 0053.40602
[22] Schützenberger, M. P., Codes à longueur variable, (Perrin, D., Theórie des codes LITP (1977)), 247-271
[23] Vincent, M., Construction de codes indécomposables, RAIRO Inform. Théor. Appl., 19, 165-178 (1985) · Zbl 0567.68046
[24] Zhang, L.; Gu, C., Factorization of 4-codes, (Second Colloq. on Words, Languages and Combinatorics. Second Colloq. on Words, Languages and Combinatorics, Kyoto, Japan (1992))
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.