×

On completion of codes with finite deciphering delay. (English) Zbl 0722.94006

Summary: We show a construction to embed a code with finite deciphering delay into a complete one, which preserves rationality and thinness properties. In consequence, each rational (thin) code with finite deciphering delay is included in a rational (thin) maximal code with the same delay.

MSC:

94A45 Prefix, length-variable, comma-free codes
20M35 Semigroups in automata theory, linguistics, etc.
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Berstel, J.; Perrin, D., Theory of Codes (1985), Academic Press: Academic Press New York, London · Zbl 1022.94506
[2] V. Bruyère, Maximal codes with bounded deciphering delay, Theoret. Comput. Sci. (1990), to appear.; V. Bruyère, Maximal codes with bounded deciphering delay, Theoret. Comput. Sci. (1990), to appear.
[3] Ehrenfeucht, A.; Rozenberg, G., Each regular code is included in a regular maximal code, RAIRO Informat. Theory,, 20, 89-96 (1985) · Zbl 0609.68053
[4] Nivat, M., Eléments de la théorie des codes, (Caianiello, E., Automata Theory (1966), Academic Press: Academic Press New York, London), 278-294 · Zbl 0208.45101
[5] Perrin, D., Completing biprefix codes, Lecture Notes in Computer Science,, 140, 397-406 (1982) · Zbl 0485.68075
[6] Restivo, A., On codes having no finite completions, Discr. Math.,, 17, 309-316 (1977) · Zbl 0357.94011
[7] Schützenberger, M. P., Une théorie algébrique du codage, (Séminaire Dubreil-Pisot 1955-56 (1955)), exposé no. 15 · Zbl 0053.40602
[8] Schützenberger, M. P., On a question concerning certain free submonoids, J. Combin. Theory,, 1, 437-442 (1966) · Zbl 0158.02302
[9] Limin Wang, Liang Zhang, Construction to embed a code with finite deciphering delay into a complete code, Acta Math. Sin., (1989), to appear.; Limin Wang, Liang Zhang, Construction to embed a code with finite deciphering delay into a complete code, Acta Math. Sin., (1989), to appear.
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.