Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$?)

share|improve this question
This is a question that I was planned to ask myself indeed. The situation for B consisting of only one forbidden word is very clear and it is described e.g. in Knuth-Graham-Patashnik's book "Concrete mathematics". –  Pietro Majer Nov 7 '10 at 19:23
add comment

1 Answer

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.

share|improve this answer
For clarity, it would be good to define abbreviations like DFA (deterministic finite automaton) and WQO (well-quasi-ordering) that many people are probably not familiar with. The WQO property for the subword relation is a consequence of the Robertson-Seymour graph minor theorem en.wikipedia.org/wiki/Robertson–Seymour_theorem, but this is far more powerful than needed. It can be proven by induction on the size of the alphabet. –  Bill Thurston Nov 8 '10 at 19:00
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.