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.


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


[1] Berstel, J.; Perrin, D., Theory of codes, (1985), Academic Press New York, London · Zbl 1022.94506
[2] 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, (), 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, (), 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.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.