De Bruijn sequences of order n represent the set A~n of all words of length n over a given alphabet A in the sense that they contain occurrences of each of these words. Recently, the computational problem of representing subsets of A~n by partial words, which are sequences that may have holes that match each letter of A, was considered and shown to be in NP. However, membership in P remained open. In this paper, we show that deciding if a subset is representable can be done in polynomial time. Our approach is graph theoretical.
展开▼
机译：De Bruijn Order N序列N将长度N的设置A〜N表示在给定的字母表A中，其意义上包含这些单词中的每一个的发生。最近，通过部分单词表示A〜N的子集的计算问题，这是可以具有匹配A的每个字母的孔的序列，并显示为NP。但是，P中的成员仍然是开放的。在本文中，我们示出了决定如果子集是可表示的，则可以在多项式时间中完成。我们的方法是图形理论。
展开▼
