Representable Sets

F. Blanchet-Sadri       Sean Simmons

Abstract    Paper    Implementation

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 subw(n) the set of subwords of w of length n, that is, 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 = subw(n) for some integer n and partial 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 our new concept of representability.

Keywords: Combinatorics on words; Partial words; Subword complexity; Representable sets.