Question

Fix an alphabet $A$ and consider words of length $n$ over $A$. Fix a set $B$ of $k$ forbidden subwords (subword is not necessarily connected, i.e. $abb$ is a subword of $abcb$). Can anything be said about the asymptotics of number of permissible words (i.e. words that don't containt any word from $B$ as a subword)? (a particular case - what if $n=k^{1+\epsilon}$ and we let $k \rightarrow \infty$?)

Answer 1

If you fix $B$ then the situation is described by a DFA (deterministic finite automaton), i.e. the set of permissible words is a regular language, and so has a rational generating function; therefore, the number of permissible words grows either exponentially or polynomially.

Re your general question, if you take $B = \{ a : a \in A \}$ (or better, $B$ consists of the empty word) then there are no permissible words. On the other hand, if all the words in $B$ have size greater than $n$, then all words are permissible. So $n = k^{1+\epsilon}$ is not really meaningful.

Maybe you're worried that the last example (all words in $B$ are bigger than $n$) is cheating. You can take $A = \{a,b,c,d\}$ and $B = \{a^kb^{m-k} : 0 \leq k \leq m \}$. The set $B$ is reduced (i.e. no word is a subword of any other word), and yet the number of permissible words is exponential; we can construct such sets $B$ with arbitrary size.

It seems reasonable (see Bill's comment below) to assume that the set of words under the subword relation is a wqo (well-quasi-ordering), and so there is no infinite reduced $B$. Therefore we can't ask whether there's an infinite reduced $B$ which allows exponential growth; if $B$ need not be reduced, take $B = \{a^m : m \geq 1\}$.

Edited to explain the acronyms re Bill's comment.