About prefix sets of words (Q1122006)

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.