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

  • $\begingroup$ 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$. $\endgroup$ Apr 8 '16 at 9:30
  • 2
    $\begingroup$ @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. $\endgroup$ Apr 8 '16 at 12:41
  • 2
    $\begingroup$ As the OP points out this is a well quasi order by Higman. $\endgroup$ Apr 8 '16 at 12:57
  • $\begingroup$ You might try the cs stackexchange. The buzzwords you want are shuttle ideal and piecewise testable $\endgroup$ Apr 8 '16 at 13:46
  • 1
    $\begingroup$ @BenjaminSteinberg [shuttle]-->[shuffle] ? $\endgroup$ Apr 10 '16 at 21:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.