An answer to a question about finite maximal prefix sets of words (Q1107641)

A set X of words over a finite alphabet is said to be prefix if no element of X is a proper left factor of another element of X. The concatenation product XY of two sets of words X and Y is unambiguous if each \(w\in XY\) admits a unique factorization \(w=xy\) with \(x\in X\) and \(y\in Y\). The concatenation product of two maximal prefix sets is itself maximal prefix. Conversely, \textit{M. P. Schützenberger} proved that, if XY is a finite maximal prefix unambiguous product, then X and Y are maximal prefix sets [Bull. Soc. Math. Fr. 93, 209-223 (1965; Zbl 0149.026)]. It is easy to provide counter-examples if the finiteness hypothesis on XY is dropped. The question addressed by the author is whether the unambiguity hypothesis is also essential. She exhibits an example of a finite maximal prefix product XY over a two-letter alphabet where: a) X is a set with three elements which is not prefix and b) Y is a prefix set for which the smallest prefix set containing it has another 7 elements. Based on techniques and results developed in another paper [Semigroup Forum 36, 147-157 (1987; Zbl 0617.20041)], she also shows that, in a certain sense, her example is minimal.