On codes having no finite completions. (English) Zbl 0357.94011

Let \(X^*\) denote the free monoid generated by the set \(X\). A subset \(A\) of \(X^*\) is called a code if \(A^*\) is a free submonoid of \(X^*\) of base \(A\). A code \(A\) in \(X^*\) is called complete if it is no proper subset of any other code in \(X\). The main result of this paper is that there exist finite codes which are not contained in any finite complete code or equivalently that in a free monoid there exist finitely generated free submonoids that are not contained in any maximal finitely generated free submonoid. Also a characterization of all finite complete codes \(A\) on the alpha-bet \(X=\{x,y\}\) of the form \(A\subset x^* \cup x^*yx^*\) is given.
Reviewer: Fred Sobik


94B60 Other types of codes
68Q45 Formal languages and automata
20M35 Semigroups in automata theory, linguistics, etc.
Full Text: DOI


[1] Krasner, M.; Ranulac, B., Sur une propriété des polynomes de la division du cercle, C.R. acad. sci. Paris, 204, 397-399, (1937) · JFM 63.0044.03
[2] Mandelbrot, B., On recurrent noise limiting codes, Proc. symp. inf. networks, 205-221, (1954), Brooklyn
[3] Nivat, M., Elements de la théorie generale des codes, (), 278-294 · Zbl 0208.45101
[4] Schützenberger, M.P., On an application of semigroup methods to some problems in coding, IRE trans. inf. theory, 47-60, (1956), I.T.2
[5] M.P. Schützenberger, Une Théorie algébrique du codage, Séminaire Dubreil-Pisot, année 55-56, exposé n. 15 (Int. Henry Poincaré, Paris).
[6] Schützenberger, M.P.; Marcus, R.S., Full decodable code word sets, IRE trans. inf. theory, 12-15, (1959), I.T.5
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.