Deciding representability of sets of words of equal length

作者：Blanchet Sadri F^*; Simmons Sean

来源：Theoretical Computer Science, 2013, 475: 34-46.

DOI：10.1016/j.tcs.2012.12.042

• Computational problems
• Algorithms
• Complexity classes P and NP
• Combinatorics on words
• Partial words
• Subwords
• Representable sets

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.

• 出版日期2013-3-4