most recent 30 from http://mathoverflow.net 2013-05-21T23:14:27Z http://mathoverflow.net/feeds/question/45182 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/45182/asymptotics-for-forbidden-subwords Marcin Kotowski 2010-11-07T17:06:44Z 2010-11-08T19:58:39Z

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

http://mathoverflow.net/questions/45182/asymptotics-for-forbidden-subwords/45184#45184 Yuval Filmus 2010-11-07T17:54:48Z 2010-11-08T19:58:39Z

<p>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.</p> <p>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.</p> <p>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.</p> <p>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\}$.</p> <p>Edited to explain the acronyms re Bill's comment.</p>