On Minimal Sturmian Partial Words

Partial words, which are sequences that may have some undefined positions called holes, can be viewed as sequences over an extended alphabet A_diamond=A cup {diamond}$ where {diamond} stands for a hole and matches (or is compatible with every letter in A. The subword complexity of a partial word w, denoted by p_w(n), is the number of distinct full words (those without holes) over the alphabet that are compatible with factors of length n of w. A function f: N -> N is (k,h)-feasible if for each integer N geq 1, there exists a k-ary partial word w with h holes such that p_w(n) = f(n) for all n, 1 = 3$holes. Finally, we give upper bounds on the lengths of minimal partial words with respect to f(n)=2n$ which are tight for h=0, 1 or 2