For a language $L$ over the finite alphabet $\Sigma$, let $L_n$ denote the set of words in $L$ of length $n$. The word $u$ is a subword of $w$ if $u$ can be obtained from $w$ by deleting letters (another term for this is subsequence, as the letters of $u$ do not need to occur consecutively in $w$). The language $L$ is subword-closed if $u\in L$ whenever $u$ is a subword of a word $w\in L$. It can be shown (see below) that for all subword-closed languages $L$, $$ \lim_{n\to\infty} \sqrt[n]{|L_n|} $$ exists and is an integer. Does anyone know of a reference for this fact? (I have stated it with proof in one of my papers, but I am trying to find the "correct" reference for it now.)
Here is the proof I know, thanks to Michael Albert. First, if $L$ is subword-closed then there are only finitely many minimal (in the subword ordering) words not in $L$ by Higman's Theorem (words over a finite alphabet are well-quasi-ordered by the subword order). This fact implies that all subword-closed languages are regular.
Next we claim that every subword-closed language $L\subseteq\Sigma^\ast$ can be expressed as a finite union of regular expressions of the form $\ell_1\Sigma_1^\ast\cdots\ell_k\Sigma_k^\ast\ell_{k+1}$ for letters $\ell_i\in\Sigma$ and subsets $\Sigma_i\subseteq\Sigma$. This follows by induction on the regular expression defining $L$. The base cases where $L$ is empty or a single letter are trivial. If the regular expression defining $L$ is a union or a concatenation then the claim follows inductively. The only other case is when this regular expression is a star, $L=E^\ast$. In this case though, because $L$ is subword-closed, we see that $L=\Pi^\ast$ where $\Pi\subseteq\Sigma$ is the set of all letters occurring in $E$.
With this claim established, it follows that $\lim\sqrt[n]{|L_n|}$ is equal to the size of the largest set $\Sigma_i$ occurring in such an expression for $L$.
