Deciding representability of sets of words of equal length (Q1939274)

The authors investigate the complexity of the problem {\textsc{Rep}} of the representability of a set \(S\) of words of equal length \(n\) by a partial word \(w\) such that \(S\) is precisely the set of all subwords of \(w\) of length \(n\), i.e., \(S\) is the set of all words compatible with factors of \(w\) of length \(n.\) A partial word may contain, besides the symbols of the alphabet, holes -- positions compatible with any alphabet symbol. As well, a variant \(h\)-{\textsc{Rep}} is considered requiring \(w\) to contain exactly \(h\) gaps. It is shown that {\textsc{Rep}} belongs to the class NP, while a deterministic polynomial algorithm is described for constructing a solution to \(h\)-{\textsc{Rep}}. The question whether {\textsc{Rep}} belongs to the class P remains open.