Computing generalized de Bruijn sequences (Q1680534)

A \textit{de Brujin sequence} of order \(n\) is a cyclic sequence over an alphabet \(A\) where each of the words of length \(n\) over \(A\) occurs as a subword exactly once. A \textit{partial word} over an alphabet \(A\) is a sequence from \(A_{\diamond} = A \cup \{ \diamond \}\), where \(\diamond \notin A\) is a symbol, called the \textit{hole symbol}, which matches every letter in \(A\). A \textit{subword} of a partial word \(w\) is a word over \(A\) that can be obtained from a factor of \(w\) by replacing the holes with letters of \(A\). A set \(S\) of words of length \(n\) over \(A\), is said to be \textit{representable} if there exists a partial word \(w\) such that the set of subwords of \(w\) of length \(n\) is exactly \(S\). The computational problem of representing subsets of \(A^n\) by partial words was shown to be in \(\mathcal{NP}\). In this paper, the authors show that this problem is actually in \(\mathcal{P}\). In particular, they describe an algorithm that, given a subset \(S\) of \(A^n\), decides in polynomial time (in the size \(n|S|\) of the input) whether \(S\) is represented by a partial word or not and, in the positive case, gives the partial word representing the set.