Some results on finite maximal codes. (English) Zbl 0578.68062

Summary: In the free monoid \(\{a,b\}^*\), we give a definition of maximality and completeness of a code with respect to the set \(T_ k\) of all words containing at most k occurrences of b. We show that the intersection of a finite maximal code with \(T_ k\) is maximal with respect to \(T_ k\), for all k. We derive some necessary conditions for a finite code to have a finite completion and we prove for these codes a ”local” version of a theorem of Schützenberger.


68Q45 Formal languages and automata
20M35 Semigroups in automata theory, linguistics, etc.
Full Text: EuDML


[1] 1. J. BERSTEL and D. PERRIN, Théorie des Codes, L.I.T.P., Université VI et VII, 1981.
[2] 2. C. DE FELICE, On the Triangle Conjecture, Inf. Proc. Letters, Vol.14, 1982, pp. 197-200. Zbl0487.68074 MR677894 · Zbl 0487.68074 · doi:10.1016/0020-0190(82)90013-8
[3] 3. S. EILENBERG, Automata, Languages and Machines, Vol. A, Academic Press, New York, 1974. Zbl0317.94045 MR530382 · Zbl 0317.94045
[4] 4. G. HANSEL, Baïonnettes et cardinaux, Discr. Math., Vol. 39, 1982, pp. 331-335. Zbl0486.20032 MR676198 · Zbl 0486.20032 · doi:10.1016/0012-365X(82)90156-X
[5] 5. M. KRASNER and B. RANULAC, Sur une propriété des polynômes de la division du cercle, C.R. Acad. Sc., Paris, T. 240, 1937, pp. 397-399. JFM63.0044.03 · JFM 63.0044.03
[6] 6. D. PERRIN and M. P. SCHÜTZENBERGER, Un problème élémentaire de la théorie de l’information, Coll. Internat, du C.N.R.S., No. 276, Théorie de l’Information, 1977, pp. 249-260. Zbl0483.94028 MR579122 · Zbl 0483.94028
[7] 7. D. PERRIN and M. P. SCHÜTZENBERGER, A Conjecture on Sets of Differences of Integer Pairs, Bull. E.A.T.C.S. Vol. 5, 1978, pp. 27-29; J. Comb. Theory, Ser B, Vol. 30, 1981, pp. 91-93. Zbl0468.05033 MR609599 · Zbl 0468.05033 · doi:10.1016/0095-8956(81)90096-4
[8] 8. J. E. PIN and I. SIMON, A Note on the Triangle Conjecture, J. Comb. Theory, Ser. A, Vol. 32, 1982, pp. 106-109. Zbl0472.05010 MR640631 · Zbl 0472.05010 · doi:10.1016/0097-3165(82)90069-3
[9] 9. A. RESTIVO, On Codes Having no Finite Completions, Discr. Math., Vol. 17, 1977, pp. 309-316. Zbl0357.94011 MR498922 · Zbl 0357.94011 · doi:10.1016/0012-365X(77)90164-9
[10] 10. M. P. SCHÜTZENBERGER, Une théorie algébrique du codage, C.R. Acad. Sc., Paris, T. 242, 1956, pp. 862-864. MR75169
[11] 11. P. SHOR, A Counterexample to the Triangle Conjecture, J. Comb. Theory, Ser. A, Vol. 38, 1985, pp. 110-112. Zbl0558.20032 MR773566 · Zbl 0558.20032 · doi:10.1016/0097-3165(85)90032-9
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.