Subwords in Partial Words
F. Blanchet-Sadri, Katie McKeon and Sinziana Munteanu
Abstract
Abstract

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. It was shown that for each non-negative integer h and each positive integer N, there exists a binary partial word w with h holes such that subw(n) has size 2n for all n = 1, 2, ..., N. Here, we consider the classification of all such partial words of minimal length. Our motivation is the construction of binary de Bruijn partial words of order n, which are partial words over the binary alphabet {a,b} of minimal length containing all the length n subwords; these partial words are said to represent the set {a,b}n. More generally, a partial word w represents a set S of words of equal length n if S = subw(n). Using a graph theoretical approach, we also investigate some computational problems related to this concept of representability.


Keywords

Combinatorics on Words; Graph Theory; Algorithms; Partial Words; Subwords; Representable Sets.