13
$\begingroup$

This question is migrated from MathOverflow, where it did not receive any answers a year ago.

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 subsequence of $w$ if $u$ can be obtained from $w$ by deleting letters (note that $u$ does not have to occur consecutively in $w$). The language $L$ is subsequence-closed if whenever $w\in L$ and $u$ is a subsequence of $w$ then $u\in L$ (thus subsequence-closed languages are piecewise testable, but not vice versa). It can be shown (see below) that for all subsequence-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, subsequence-closed languages are necessarily regular (if $L$ is subsequence-closed then there are only finitely many minimal words not in $L$ by Higman's Lemma, and this leads quickly to the existence of a regular expression for it).

Next we claim that every subsequence-closed language $L\subseteq\Sigma^\ast$ can be expressed as a finite union of regular expressions of the form $$ \ell_1\Sigma_1^\ast\ell_2\Sigma_2^\ast\cdots\ell_k\Sigma_k^\ast\ell_{k+1} $$ for letters $\ell_i\in\Sigma$ and subsets $\Sigma_i\subseteq\Sigma$. (I would also be interested if anyone has a reference for this decomposition of subsequence-closed languages.) 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, say $L=E^\ast$ for a regular expression $E$. In this final case we see that $L=\Pi^\ast$ where $\Pi\subseteq\Sigma$ is the set of all letters occurring in $E$ because $L$ is subsequence-closed.

With the claim above 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$.

$\endgroup$
  • 3
    $\begingroup$ Not really an answer, but subsequence-closed languages appear to be called "strictly piecewise languages" in the formal language literature. This may help track down references to their growth rate. $\endgroup$ – David Eppstein Jun 4 '17 at 21:05
  • 3
    $\begingroup$ I am not sure to understand your decomposition result, since the regular expressions of the form $\ell_1\Sigma_1^\ast\ell_2\Sigma_2^\ast\cdots\ell_k\Sigma_k^\ast\ell_{k+1}$ are not necessarily closed under taking subsequences: for instance $acb$ belongs to $ac^*b$, but $c$ does not. Did I miss something? $\endgroup$ – J.-E. Pin Jun 16 '17 at 14:17
  • 1
    $\begingroup$ @J.-E.Pin, the claim is that subsequence-closed languages are finite unions of such regular expressions. In your example of $ac*b$, any subsequence-closed language which contained that regular expression would also have to contain $ac*$, $c*b$, and $c*$. $\endgroup$ – Vince Vatter Jun 19 '17 at 14:07

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.