On codes having no finite completions
type: Item
instance of: scholarly article
title: On codes having no finite completions
zbMATH Open document ID: 0357.94011
DOI: 10.1016/0012-365X(77)90164-9
author: Antonio Restivo
published in: Discrete Mathematics
publication date: 1977-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 94B60
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 20M35
zbMATH DE Number: 3557657
MaRDI profile type: Publication
cites work: Q5610821
full work available at URL: 0012-365x(77)90164-9
OpenAlex ID: W2062991407
description: scientific article; zbMATH DE number 3557657