On minimal Sturmian partial words (Q534335)

The subword complexity \(p_w (n)\) of a word \(w\) is the function that maps \(n\) to the number of distinct length-\(n\) factors occurring in \(w\). A partial word is a word with a ``don't care'' symbol \(\diamond\) that matches every other symbol. The notion of subword complexity can be extended to partial words \(w\) by counting the total number of ordinary words that are compatible with length-\(n\) factors of \(w\). In this paper, the authors show that, for all integers \(h, N \geq 0\), there exist partial words \(w\) with \(h\) holes such that \(p_w (n) = n + 1\) for \(1 \leq n \leq N\). They also study the length of the shortest such words and the number of minimal words. They also consider similar questions where \(n + 1\) is replaced by \(2n\).