Let \(x\) be a word of length \(n\), \(n \geq 0\), on a fixed alphabet. A \textit{superword} of \(x\) is of the form \(uxv\), where \(u, v\) may be empty. A word \(y\) of length \(m\), \(m< n\), is a \textit{cover} of \(x\) if there exists a set of positions \(P \subseteq \{1, \ldots, n-m+1\}\) such that \(y=x[i..i+m-1]\) for all \(i \in P\) and \(\bigcup_{i \in P} \{i, \ldots, i+m-1\}=\{1, \ldots, n\}\). A word is a \textit{seed} of \(x\) if it is a cover of a superword of \(x\). In this very interesting paper, the authors study the frequency of seeds that can appear in a word. They derive an \(O(n)\) upper bound for the average number of seeds in a word of length \(n\), and both an \(\frac{1}{6}n^2+o(n^2)\) lower bound and an \(\frac{1}{4}n^2+o(n^2)\) upper bound for the maximum number of distinct seeds in such a word, denoted by \(\operatorname{Seeds}(n)\). They also establish some properties on the structure of the extremal word that maximizes \(\operatorname{Seeds}(n)\). An important note is that seeds have been restricted to be factors of the given word. Bounds exist in the literature on the maximum number of other types of distinct regularities such as runs, cubic runs, squares, and cubes.
This page was built for publication: On the appearance of seeds in words
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2809942)
