×

On codes having no finite completion. (English) Zbl 0819.94019

Summary: For each natural numbers \(n\geq 5\) and \(n\neq 6\), we propose a class of finitely incompletable codes that contain \(a^ n\) on a binary alphabet \(\{a,b\}\). The construction is essentially based on unambiguous pairs unembeddable to a factorization of \(\mathbb{Z}_ n\).

MSC:

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

References:

[1] 1. J. BERSTEL and D. PERRIN, Theory of Codes, Academic Press, New York, 1985. Zbl0587.68066 MR797069 · Zbl 0587.68066
[2] 2. V. BRUYÈRE, LIMIN WANG and LIANG ZHANG, On Completion of Codes with Finite Deciphering Delay, European Journal of Combinatorics, 1990, 16, pp. 513-521. Zbl0722.94006 MR1078707 · Zbl 0722.94006 · doi:10.1016/S0195-6698(13)80036-4
[3] 3. C. DE FELICE, Construction of a Family of Finite Maximal Codes, Theoretical Computer Science, 1989, 63, pp. 157-184. Zbl0667.68079 MR984315 · Zbl 0667.68079 · doi:10.1016/0304-3975(89)90076-5
[4] 4. C. DE FELICE and A. RESTIVO, Some Results on Finite Maximal Codes, RAIRO Informatique théorique, 1985, 19, pp. 383-403. Zbl0578.68062 MR827484 · Zbl 0578.68062
[5] 5. A. EHRENFEUCHT and G. ROZENBERG, Each Regular Code Is Included in a Regular Maximal Code, Rairo Informatique théorique, 1986, 16, pp. 89-96. Zbl0609.68053 MR849968 · Zbl 0609.68053
[6] 6. L. FUCHS, Abelian Groups, Akadémiai kiadó, Budapest, 1958, Pergamon Press, Oxford-London-New York-Paris, 1960. MR111783
[7] 7. M. KRASNER and B. RANULAC, Sur une propriété des polynômes de la division du cercle, C.R. Acad. Sci. Paris, 1937, 240, pp. 297-299. Zbl0015.38601 JFM63.0044.03 · Zbl 0015.38601
[8] 8. G. LALLEMENT, Semigroups and Combinatorial Applications, John Wiley and Sons, New York, 1979, 1969. Zbl0421.20025 MR530552 · Zbl 0421.20025
[9] 9. Al A. MARKOV, An Example of Independent System of Words Which Cannot Be Included into a Finite Complete System, Matematicheskie Zametki, 1967, 1, No. 1, pp. 87-90 (in Russian). Zbl0154.00703 MR210594 · Zbl 0154.00703
[10] 10. A. RESTIVO, On Codes Having no Finite Completions, Discrete Mathematics, 1977, 17, pp. 309-316. Zbl0357.94011 MR498922 · Zbl 0357.94011 · doi:10.1016/0012-365X(77)90164-9
[11] 11. A. RESTIVO, S. SALEMI and T. SPORTELLI, Completing Codes, RAIRO Informatique théorique, 1989, 23, pp. 135-147. Zbl0669.94012 MR1001722 · Zbl 0669.94012
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.