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

Improve this question
$\endgroup$
3
  • 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, 2017 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, 2017 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, 2017 at 14:07

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.