×

Maximal circular codes versus maximal codes. (English) Zbl 1005.94014

From the introduction: The theory of codes is closely concerned with the two notions of completeness and maximality, the equivalence of which has been established for famous families of codes such as thin codes, thin circular codes, thin codes with finite deciphering delay and thin codes with finite synchronization delay. Recently, the author established this equivalence for the so-called class of code with finite interpreting delay [Y. Guesnet, Theor. Inform. Appl. 34, 47-59 (2000; Zbl 0978.94047), On maximal codes with finite interpreting delay, Theor. Comput. Sci. 273, No. 1, 167-183 (2002; Zbl 1050.68040)].
More precisely, let \({\mathcal F}\) be one of the previous families and let \(X\in{\mathcal F}\). Then \(X\) is complete if and only if \(X\) is maximal in \({\mathcal F}\). These families of codes even satisfy a stronger equivalence: \(X\) is maximal in \({\mathcal F}\) if and only if \(X\) is maximal in the general family of codes. The proofs of this result are based on the particular case of thin codes.
This paper answers a question of De Luca and Restivo of whether there exists a circular code that is maximal as a circular code and not as a code. The author exhibits a circular code that is maximal in the family of circular codes and not maximal in the family of codes.

MSC:

94A45 Prefix, length-variable, comma-free codes
94B60 Other types of codes
94B15 Cyclic codes
68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI Numdam EuDML

References:

[1] J. Berstel and D. Perrin , Theory of Codes . Academic Press ( 1985 ). MR 797069 | Zbl 0587.68066 · Zbl 0587.68066
[2] V. Bruyère , Codes , Dissertation présentée pour l’obtention de grade légal de docteur en sciences. Université de Mons-Hainaut ( 1991 ). · Zbl 0737.68049
[3] V. Bruyère , On maximal codes with bounded synchronization delay . Theoret. Comput. Sci., 204 ( 1998 ) 11 - 28 . MR 1637488 | Zbl 0913.68160 · Zbl 0913.68160 · doi:10.1016/S0304-3975(98)00028-0
[4] A. de Luca and A. Restivo , On some properties of very pure codes . Theoret. Comput. Sci., 10 ( 1980 ) 157 - 170 . MR 551602 | Zbl 0421.68078 · Zbl 0421.68078 · doi:10.1016/0304-3975(80)90012-2
[5] Y. Guesnet , On codes with finite interpreting delay: A defect theorem . Theoret. Informatics Appl., 34 ( 2000 ) 47 - 59 . Numdam | MR 1771129 | Zbl 0978.94047 · Zbl 0978.94047 · doi:10.1051/ita:2000106
[6] Y. Guesnet , Codes et interprétations , Thèse de doctorat. Université de Rouen ( 2001 ). MR 1879770 · Zbl 1005.94014
[7] Y. Guesnet , On maximal codes with finite interpreting delay . Theoret. Comput. Sci., (to appear). Zbl 1050.68040 · Zbl 1050.68040 · doi:10.1016/S0304-3975(00)00439-4
[8] M.P. Schützenberger , Une théorie algébrique du codage , in: Séminaire Dubreil-Pisot 1955 - 56 Institut H. Poincaré ( 1956 ), Exposé n\({}^\circ \)15. Numdam | MR 75169
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.