Subwords of Partial Words

F. Blanchet-Sadri, Mark Heimann, Andrew Lohr

Abst Implementation Paper

Given a partial word \(w\), we denote by \(sub_w(n)\) the set of subwords of \(w\) of length \(n\), i.e., words that are compatible with factors of \(w\) of length \(n\). We call a set \(S\) of words representable if \(S = sub_w(n)\) for some integer \(n\) and partial word \(w\). Using a graph theoretical approach, it was shown that the problem of whether a given set is representable can be decided in polynomial time. It was also shown how to construct representing partial words. Here we consider the construction of minimal representing partial words. Can this be done efficiently?

Related to the question of representability is the concept of subword complexity. In particular, we can say that a partial word \(w\) is \(2n\)-complex of order N if, for each \(n \le N\), \(|sub_w(n)| = 2n\). Here we undertake the classification of minimally \(2n\)-complex words: the shortest length \(2n\)-complex words with a given number of holes \(h\) and a given order \(N\). We investigate methods for constructing such words, as well as for determining their length and how many there are.

Keywords: Combinatorics on words; Partial words; Subwords; Representable sets.