Deciding representability of sets of words of equal length

摘要

Partial words are sequences over a finite alphabet that may have holes that match, or are compatible with, all letters in the alphabet; partial words without holes are simply words. Given a partial word w, we denote by sub_w (n) the set of subwords of w of length n, i.e., words over the alphabet that are compatible with factors of w of length n. We call a set S of words h-representable if S = sub_w (n) for some integer n and partial word w with h holes. Using a graph theoretical approach, we show that the problem of whether a given set is h-representable can be decided in polynomial time. We also investigate other computational problems related to this concept of representability.