Periodicity algorithms and a conjecture on overlaps in partial words (Q442242)

An alphabet \(A\) is a nonempty finite set of symbols (letters). Let \(A_{\diamond}=A\cup\{\diamond\}\) be the alphabet \(A\) extended by the hole symbol \(\diamond\). A finite sequence of letters from \(A\) is called a full word over \(A\). A partial word over \(A\) is a finite sequence of symbols from \(A_{\diamond}\). A partial word \(u\) is said to be contained in a partial word \(v\), if \(u\) and \(v\) have the same length and \(u_i=v_i\) for all \(u_i\in A\). For a given \(d\in \mathbb{N}\), a partial word \(u\) is called \(d\)-valid if the letters of \(u\) at positions \(i\) and \(j\) are not both holes for all \(i,j\in \mathbb{N}_0\) satisfying \(0<|i-j|\leq d\). For a given \(p\in \mathbb{N}\), a partial word \(u\) is called (strongly) \(p\)-periodic if \(u_i=u_j\) whenever \(u_i,u_j\in A\) and \(i\equiv j \mod p\). In this paper, the authors study the problem of construction of \(p\)-periodic partial words contained in a given full word. They propose an \(O(nd)\) time algorithm which for a full word \(w\), given as input, outputs a \(p\)-periodic \(d\)-valid partial word contained in \(w\) if such a partial word exists. The second achievement of the paper consists in giving an affirmative answer to a conjecture by the first two authors and \textit{G. Scott} [Theor. Comput. Sci. 410, No. 8--10, 793--800 (2009; Zbl 1162.68029)]. Namely, the authors construct an infinite word over a five-letter alphabet that remains overlap-free after holes are inserted in arbitrary \(2\)-valid positions.