Primitive sets of words (Q2662680)

The paper introduces the notion of a \emph{primitive set}, which is a set \(X\) such that the monoid \(M\) generated by \(X\) is not a proper submonoid of a monoid generated by at most \(|X|\) words. The monoid \(M\) is then called \(k\)-maximal with \(k = |X|\). The property of a set being primitive is stronger than the known property of being elementary. The paper shows that the intersection of two \(2\)-maximal submonoids is either empty or generated by a single primitive word. This in particular implies that a set \(X\) of rank two has a unique primitive root, that is, a primitive set \(Y\) such that \(X\) is contained in the monoid generated by \(Y\). The same does not hold for higher ranks. The paper also introduces the notion of a \emph{bi-root} of a word \(w\), which is a primitive set \(\{x,y\}\) such that \(w\) is in the monoid generated by \(\{x,y\}\). It is shown that there is at most one bi-root satisfying \(|x| + |y| < \sqrt{|w|}\). The results are also applied to pseudo-repetitions introduced in [\textit{E. Czeizler} et al., Theor. Comput. Sci. 411, No. 3, 617--630 (2010; Zbl 1184.68311)].