# Reference request: exponential growth rates of subword-closed languages are integers

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$$.

• The claim about finiteness of the set of minimal words not in $L$ looks strange. Do you need exponential growth to state it? Otherwise it is false, as the language $\{a^kb^\ell a^m\colon k,\ell,m\geq 0\}$ shows. The minimal words not in $L$ are $ba^{k+1}b$ for all $k\geq 0$. Apr 8 '16 at 9:30
• @IlyaBogdanov, subword in the op sense means deleting letters so subsequence if you view words as a sequence of letters. So bab is a subword if all $ba^{k+1}b$ and is the unique minimal forbidden subword. Apr 8 '16 at 12:41
• As the OP points out this is a well quasi order by Higman. Apr 8 '16 at 12:57
• You might try the cs stackexchange. The buzzwords you want are shuttle ideal and piecewise testable Apr 8 '16 at 13:46
• @BenjaminSteinberg [shuttle]-->[shuffle] ? Apr 10 '16 at 21:59