About prefix sets of words
type: Item
instance of: scholarly article
title: About prefix sets of words
zbMATH Open document ID: 0675.20056
DOI: 10.1016/0097-3165(89)90048-4
author: Véronique Bruyère
published in: Journal of Combinatorial Theory. Series A
publication date: 1989-01-01T00:00:00Z
review text: A subset X of the free monoid \(A^*\) over the alphabet A is called prefix iff it satisfies the property: uv\(\in X\) and \(u\in X\) \(\Rightarrow\) \(v=1\). A set \(X\subset A^*\) is then called maximal prefix if it is prefix and not strictly contained in an other prefix subset of \(A^*\). It is easy to see that the concatenation product of two maximal prefix sets is also maximal prefix. A converse of this result was proved by \textit{M. P. Schützenberger} [Bull. Soc. Math. Fr. 93, 209-223 (1965; Zbl 0149.026)] under the hypotheses that X, Y are finite and that the product XY is unambiguous (for more details concerning this theorem or prefix sets, see \textit{J. Berstel} and \textit{D. Perrin} [Theory of Codes (1985; Zbl 0587.68066)]). Here, the author generalizes Schützenberger's result to the non finite case. It is proved that for every sets \(X,Y\subset A^*\) such that: i) \(\exists x_ 0\in X\), \(x_ 0A^+\cap X=\emptyset\), ii) \(\forall x\in X\), \(\exists n\in {\mathbb{N}}\), \(Y\cap R^ n_ xA^*=\emptyset\) where \(R_ x=\{w\in A^+\), \(x\in A^*w\}\) then, if the product XY is unambiguous and maximal prefix, X and Y are also maximal prefix. The two previous conditions are shown to be necessary.
Mathematics Subject Classification ID: 20M35
Mathematics Subject Classification ID: 94B35
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 20M05
zbMATH DE Number: 4105248
zbMATH Keywords: ambiguity
zbMATH Keywords: free monoid
zbMATH Keywords: alphabet
zbMATH Keywords: concatenation product
zbMATH Keywords: maximal prefix sets
reviewed by: Daniel Krob
MaRDI profile type: Publication
full work available at URL: 0097-3165(89)90048-4
OpenAlex ID: W195352547
cites work: Q4430300
cites work: An answer to a question about finite maximal prefix sets of words
cites work: Sur certains sous-monoïdes libres
cites work: On a question concerning certain free submonoids
description: scientific article; zbMATH DE number 4105248