<p>This question is migrated from <a href="https://mathoverflow.net/questions/235615/reference-request-exponential-growth-rates-of-subword-closed-languages-are-inte">MathOverflow</a>, where it did not receive any answers a year ago.</p>

<p>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 <em>subsequence</em> of $w$ if $u$ can be obtained from $w$ by deleting letters (note that $u$ does <em>not</em> have to occur consecutively in $w$). The language $L$ is <em>subsequence-closed</em> 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.)</p>

<p>Here is the proof I know, thanks to <a href="https://en.wikipedia.org/wiki/Michael_H._Albert" rel="noreferrer">Michael Albert</a>. 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).</p>

<p>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.</p>

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

CC BY-SA 3.0
2017-06-04T21:05:36.077Z
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.
David Eppstein
CC BY-SA 3.0
2017-06-16T14:17:15.567Z
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?
J.-E. Pin
CC BY-SA 3.0
2017-06-19T14:07:58.667Z
@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*$.
Vince Vatter
<reference-request><co.combinatorics><fl.formal-languages><regular-language><enumeration>
Reference request: exponential growth rates of subsequence-closed languages are integers
Vince Vatter
# Reference request: exponential growth rates of subsequence-closed languages are integers

(Asked by: username_0 on 2017-06-04)

This question is migrated from [MathOverflow](https://mathoverflow.net/questions/235615/reference-request-exponential-growth-rates-of-subword-closed-languages-are-inte), 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](https://en.wikipedia.org/wiki/Michael_H._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$.

**Tags:** reference-request, co.combinatorics, fl.formal-languages, regular-language, enumeration
> **Comments:**
> **username_1**: 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.  
> **username_2**: 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?  
> **username_0**: @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*$.  

---

## 0 answers

