Drw-03481 AR255

IRIA
laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 105 78150 - Le Chesnay
France
Tél.: 954 90 20

laboratoire de recherche
en informatique
et automatique

<figure><img src="image_1.png" /></figure>

A NEW COMPLEXITY MEASURE
FOR LANGUAGES

Luc BOASSON,
Bruno COURCELLE,
Maurice NIVAT

Rapport de Recherche N° 255

Octobre 1977
# A NEW COMPLEXITY MEASURE FOR LANGUAGES

Luc Boasson*, Bruno Courcelle**, Maurice Nivat***

## Résumé :

On associe à tout langage son index rationnel, une fonction croissante des entiers dans les réels. En comparant la croissance des index rationnels des langages, on les classe en hiérarchies et on définit de nouveaux cônes et anticônes rationnels.

Nous considérons plus particulièrement le cas des langages algébriques et posons plusieurs questions reliées aux conjectures encore ouvertes sur les sous-cônes de la famille des langages algébriques.

## Abstract :

We associate with every language L its rational index which is an increasing function from integers to real numbers.

The comparison between the rates of growth of these functions allows us to classify languages into hierarchies and to define a large number of new rational cones and rational anticones. We focus then our attention on the rate of growth of the rational index of context-free languages and raise several questions closely related to the open conjectures concerning the subcones of the family of context-free languages.

N.B. - Le travail a été présenté à Waterloo, «A Conference on Theoretical Computer Science», Août 1977.

N.B. - This work has been presented at Waterloo, «A Conference on Theoretical Computer Science», August 1977.

<footnote>* Université de Picardie</footnote>

<footnote>** IRIA</footnote>

<footnote>*** Université Paris VII</footnote>
# A NEW COMPLEXITY MEASURE FOR LANGUAGES

by Luc BOASSON<sup>†</sup>, Université de Picardie
Bruno CCURCELLE, IRIA<sup>*</sup>
and Maurice NIVAT<sup>†</sup>, Université Paris 7.

**Abstract** : We associate with every language L its rational index which is an increasing function $g_L$ of $N^+$ the set of strictly positive integers into $R^+$ the set of strictly positive real numbers.

The comparison between the rates of growth of these functions allows us to classify languages into hierarchies and to define a large number of new rational cones and rational anticones.

We focus then our attention on the rate of growth of the rational index of context-free languages and raise several questions closely related to the open conjectures concerning the subcones of the family of context-free languages.

**Introduction** : The rational index of a language $L \subset X^*$ is the function $g_L$ defined by :

$$g_L(n) = \max(\min(|u|/u \in L \cap R), L \cap R \neq \emptyset \text{ and } R \in \text{Rat}_n(X^*)))$$

where $\text{Rat}_n(X^*)$ is the set of rational languages which are accepted by a non deterministic finite automaton with n states.

We consider the rate of growth of $g_L(n)$ for large n as a complexity measure of L.

In fact, this complexity measure behaves properly through the AFL-operations and different rational cones and anticones can be defined in terms of this complexity.

We focus our attention on context-free languages and raise several questions closely related to the open conjectures concerning the maximal subcones of the family of context-free languages.

Here are some results, roughly stated :

1. If $L' = \tau(L)$ for some rational transduction $\tau$ then $g_L(n) \le qng_L(pn)$ for some integers p and q,

2. $g_L(n) \le 2^{pn^2}$, for some integer p if L is context-free (this upper bound should be improved),

3. $g_L(n) \le n^k$, for some integer k if L is linear, one-counter or quasirational,

4. $g_L(n) \ge 2^{pn}$ for infinitely many n if L is a fullgenerator of the AFL of context-free languages.

## PART I : The rational index of a language

By function we mean in this paper an increasing mapping of $N^+$ into $R^+$. We shall use the notation borrowed from lambda-calculus : $\lambda n·f(n)$ is the function which maps n to $f(n)$ for $n \in N^+$. For instance $\lambda n·n$ is the identity function, $\lambda n·n^2$ the square function. (But we shall also use small letters f,g,h... to denote functions).

<footnote>(†) Laboratoire d'Informatique Historique et Programmation, Université Paris VII, 2, Place Jussieu 75221 PARIS Cedex 05.</footnote>

<footnote>(*) IRIA, Rocquencourt, 78150 - Le Chesnay, France</footnote>
On the set of functions we consider the following partial pre-order : $f$ grows less fast than $g$ (or equivalently $g$ grows faster than $f$) if and only if there exists a real $p \in \mathbb{R}^+$ such that $f(n) \le pg(n)$ for almost all $n$ (equivalently : "there exists $q$ such that $n>q$ implies $f(n) \le pg(n)$" or "for sufficiently large $n$"). It is clear that the relation thus defined is a preorder (i.e. reflexive and transitive) and not an order (i.e. not antisymmetric). We denote this relation by $f \prec g$. Its negation, denoted by $f \succ g$ is equivalent to :

For all $p \in \mathbb{R}^+$ there exists an infinite subset $A$ of $\mathbb{N}$ such that for all $n \in A$, $pg(n) < f(n)$, or equivalently :

for all $p \in \mathbb{R}^+$ there exist arbitrarily large $n$ such that $pg(n) < f(n)$.

One should note that the relation $f \prec g$ differs from $g \prec f$.

Now we shall consider languages on the alphabet $X$, i.e. subsets of $X^*$. These languages will be denoted by capital letters $K, L, R, \dots$.

The family of languages on $X$ : $\mathrm{Rat}_n(X^*)$ is the family of all rational languages which can be recognized by a finite (non-deterministic) automaton with $n$ states.

If $K$ and $L$ are languages on $X$ we shall denote by $\delta_{K,L} = \min(|u|, |w|: K \in \mathrm{K} \wedge L \in \mathrm{L})$. By $|u|$, where $u \in X^*$ we denote the length of $u$.

We shall denote by $\min(\mathrm{K} \wedge \mathrm{L})$ the set :

$$ \min(\mathrm{K} \wedge \mathrm{L}) = \{u \in \mathrm{K} \wedge \mathrm{L} \mid |u| = \delta_{\mathrm{K},\mathrm{L}}\} $$

We shall be interested in the following function, associated with each language $L \in X^*$ :

$$ g_L = \lambda n \cdot \max\{\delta_{K,L} | K \in \mathrm{Rat}_n(X^*)\} $$

We call it the rational index of $L$.

Our purpose is to compare languages by comparing the rate of growth of their rational indices.

We first make a few remarks :

**Remark 1** : $g_L$ is increasing, i.e. : $g_L(n) \le g_L(n+1)$ for all $n$. This comes from the fact that $K \in \mathrm{Rat}_n(X^*)$ implies $K \in \mathrm{Rat}_{n+1}(X^*)$.

**Remark 2** : $L$ is infinite if and only if $g_L$ grows faster than $\lambda n \cdot n$.

Indeed if $L$ is infinite, $\mathrm{L}\in X^{n-1} \setminus X^*$ is not empty for all $n$. Take $u \in X^{n-1} \setminus X^*$ and $K_0 = u \in X^*$. One knows that $K_0 \in \mathrm{Rat}_n(X^*)$. Thus

$$ \delta_{K_0,L} = |u|^{n-1} \text{ and } g_L(n) = \max\{\delta_{K,L} | K \in \mathrm{Rat}_n(X^*)\} \ge \delta_{K_0,L}^{n-1}. $$

Thus for all $n \in \mathbb{N} \setminus \{1\}$, $n \le 2g_L(n)$ which means that $\lambda n \cdot n$ grows less fast than $g_L$.

Reciprocally if there exists $p \in \mathbb{R}^+$ such that for all sufficiently large $n$, $n \le pg_L(n)$ one has for all $n \in \mathbb{N}^+$ there exists $n \in \mathbb{N}$ such that $g_L(n) \ge n$ and this implies that for all $n \in \mathbb{N}^+$, $L$ contains at least a word of length $n$. $\square$

**Remark 3** : For every function $f$ which grows faster than $\lambda n \cdot n$ there exists a language $L$ such that $g_L$ grows faster than $f$ and does not grow less fast than $f$, i.e. $f < g_L$ and $g_L/f$.

Take $L = \{(x^n)^2(n+2) \mid n \in \mathbb{N}^+\}$ and the rational language $K = x^{n-2}(y^*)^*$ which belongs to $\mathrm{Rat}_n((x,y)^*)$. Clearly $K, L = n-2+n$ $f(n)$.

Whence $f(n) = g_L(n)$ for all $n$ and $f \le g_L$, and for all $p$ and $n \ge p$, $pf(n) \le g_L(n)$ whence $g_L/f \le g_L$.

We shall now establish several lemmas relating the rate of growth of $g_{L_1}, g_{L_2}, g_L^*$ and $g_L$ (where $L_1$ is the image of $L$ under a rational transduction $\tau$) with the rate of growth of $g_L$ and $g_L^*$.

**Lemma 1** : For all $n \in \mathbb{N}^+$ : $g_{L_1 L_2}(n) = \max(g_L(n), g_L^*(n))$.

**Lemma 2** : For all $n \in \mathbb{N}^+$ : $g_{L_1 L_2}(n) \le g_L(n) + g_L^*(n)$.
**Proof :** Let $K \in \text{Rat}_n^*(X^*)$ be recognized by the automaton $\langle Q, q_0, Q_f, \lambda \rangle$ where
* $Q$ is the finite set of states,
* $q_0$ is the initial state,
* $Q_f$ the set of final states,
* $\lambda$ maps $Q \times X$ into $Q^Q$.

Let $u = u_1 u_2$ where $u_1 \in L \cap K_1, u_2 \in L' \cap K_2, K_1, K_2$ being defined as the languages recognized by $\langle Q, q_0, \{q_1\}, \lambda \rangle$ and $\langle Q, q_1, Q_f, \lambda \rangle$ for some $q_1 \in \lambda(q_0, u_1)$ such that $\lambda(q_1, u_2) \cap Q_f \neq \emptyset$.

If $u_1$ (resp. $u_2$) did not belong to $\text{MIN}(L \cap K_1)$ (resp. $\text{MIN}(L' \cap K_2)$) u would not belong to $\text{MIN}(K \cap L)$.
Whence $|u_1| \leq g_1(n)$ and $|u_2| \leq g_2(n)$ which implies $|u| = |u_1| + |u_2| \leq g_1(n) + g_2(n)$.

The example of a $b^*$ as language L and $(a^b)^*$ as language K proves that lemma 2 cannot be
sharpened since $\delta_{K,L} = q+1$ and $\delta_{K,L}^2 = 2q+2$. $\square$

**Lemma 3 :** *For all* $n \in N^+$ $g_L^*(n) \le n$ $g_L(n)$.

**Proof :** Using the pumping lemma for rational languages one easily proves that if $u \in \text{MIN}(K \cap L^*)$ and $K \in \text{Rat}_n^*(X^*)$ then there exists $p \in \mathbb{N}$ such that $u \in \text{MIN}(K \cap L^p)$.

The rest of the proof is the same as the proof of lemma 2. By taking a finite L different
from $\emptyset$ and $\{1\}$, one proves that lemma 3 cannot be sharpened. $\square$

**Lemma 4 :** If $L$ and $L'$, languages on $X$, and $R \in \text{Rat}_q^*(X^*)$ are such that $L' = L \cap R$ then $g_L < \lambda n \cdot g_L(qn)$.

**Proof :** One knows that $K \in \text{Rat}_n^*(X^*)$ and $R \in \text{Rat}_q^*(X^*)$ imply that $K \cap R \in \text{Rat}_{qn}^*(X^*)$ [1] and it is clear that
$\delta_{K,L'} = \delta_{K \cap R, L'}$. Thus, for all $n$, $g_L^*(n) \le g_L(qn)$. $\square$

Note that from $g_L^* < \lambda n \cdot g_L(qn)$ one gets $\lambda n \cdot g_L^* ([n/q]) < g_L$ where $[n/q]$ denotes the largest integer $p$ such that $pq \le n$. Indeed for all sufficiently large $n$, $pq \le n < (p+1)q$ implies $g_L^* ([n/q]) = g_L^*(p) \le g_L^*(pq) \le g_L^*(n)$.

**Lemma 5 :** If $L \subseteq X$, $L' \subseteq Y$ and $\phi$ an alphabetic homomorphism of $X^*$ into $Y^*$ are such that
$L' = \phi(L)$ then $g_L^* < g_L^*(\phi(L))$.

**Proof :** One recalls that $\phi$ is alphabetic if and only if $\phi(X) \subseteq Yu\{j\}$ (1 is the empty word).
One knows that $[1]$ :

$$
\begin{align*}
\phi(L) \cap K &= \phi(L \cap \phi^{-1}(K)), \\
K \in \text{Rat}_n^*(Y^*) &\implies \phi^{-1}(K) \in \text{Rat}_n^*(X^*), \\
\text{For all } u \in X^*, \quad |\phi(u)| \le |u|.
\end{align*}
$$

Take $K \in \text{Rat}_n^*(Y^*)$ such that $\delta_{K,L'} = g_L^*(n)$

Let $v \in \text{MIN}(\phi^{-1}(K) \cap L)$. Then $\phi(v) = u$ belongs to $\phi(L) \cap K$ and $|v| \ge |u|$. Thus :

$$
\begin{gather*}
\delta_{K, \phi(L)} \le |u| \le |v| = \delta_{\phi^{-1}(K), L'} \\
\text{Since } \phi^{-1}(K) \in \text{Rat}_n^*(X^*), \quad \delta_{\phi^{-1}(K), L} \le g_L^*(n) \text{ and } g_L^*(n) \le g_L^*(n). \quad \square
\end{gather*}
$$

**Lemma 6 :** If $L' \subseteq X^*$, $L \subseteq Y^*$, and $\phi$ an alphabetic homomorphism of $X^*$ into $Y^*$ are such that $L' = \phi^{-1}(L)$ then $g_L^* < \lambda n \cdot g_L^*(n)$.

**Proof :** One knows that $\phi(\phi^{-1}(L) \cap K) = L \cap \phi(K)$ and $K \in \text{Rat}_n^*(X^*)$ implies $\phi(K) \in \text{Rat}_n^*(Y^*)$. Now take $K \in \text{Rat}_n^*(X^*)$ such that $\delta_{K,L'} = g_L^*(n)$. Consider $v \in \text{MIN}(L \cap \phi(K))$, $|v| = \delta_{\phi(K),L'} \le g_L^*(n)$. There exists in $\phi^{-1}(v) \cap K \in \phi^{-1}(L) \cap K$ a word $u$ which does not contain more than $n$ consecutive letters whose image by $\phi$ is $l$ (by a straightforward application of the pumping lemma for rational languages).

$$
\begin{align*}
& \text{Since } \delta_{K,L'} \le |u|, \text{ we get } g_L^*(n) = \delta_{K,L'} \le |u| \le n \cdot |v| + n \le n \cdot g_L^*(n) + n. \\
& \text{We can also write } g_L^*(n) \le 2n \cdot g_L^*(n) \text{ whence the result. } \square
\end{align*}
$$
Note that from $g_L$, $<\lambda n \cdot ng_L(n)$ we can infer $\lambda n \cdot g_L(n)/n < g_L$. Indeed $g_L$, $<\lambda n \cdot ng_L(n)$ means that there exists $pcN^+$ such that for all $n$ sufficiently large $g_L(n) \le pqg_L(n)$ which can be written $g_L(n) \ge \frac{1}{pn} g_L(n)$.

**Remark 4** : The lemma 6 is "optimal" as shown by the following example :

$$L = \{a^n b^m | m, n \in \mathbb{N}^+, m \neq n\}.$$

One can easily show that $g_L < \lambda n \cdot n$ (by a straightforward application of the pumping lemma).

Now take $\vdash : \{a,b,c\}^* + \{a,b\}^*$ defined by $\phi(a) = a$, $\phi(b) = b$, $\phi(c) = 1$.

The language $L' = \phi^{-1}(L)$ has a rational index $g_L$, which grows faster than $\lambda n \cdot n^2$. To show that, take $K = (ac^q)^* b^q \in \text{Rat}_{2q+1}(\{a,b,c\}^*)$ : one has $\delta_{K,L'} = q^{2+q}$. Thus $\lambda q \cdot qg_L(q) < g_L(q)$. $\square$

We now put together the three previous lemmas to get the fundamental :

**Theorem 1** : If $L \subseteq X^*$, $L' \subseteq Y^*$, and $\tau$ is a rational transduction of $X^*$ into $Y^*$ are such that $L' = \tau(L)$ then there exists $pcN^+$ such that :

$$g_L, < \lambda n \cdot ng_L (pn)$$

**Proof** : One recalls that every rational transduction $\tau$ can be written $\tau(u) = \psi(\phi^{-1}(u)nK)$ where $Z^*$ is a free monoid, $\phi$ and $\psi$ alphabetic morphisms of $Z^*$ into $X^*$ and $Y^*$ respectively and $K \in \text{Rat}(Z^*)$. [2]

And one applies the three lemmas considering that $L' = \tau(L)$ is equivalent to
$L' = \psi(\phi^{-1}(L)nK)$.

Hence
$$g_L' < g_{\phi^{-1}(L)} < K$$
$$< \lambda n \cdot g_{\phi^{-1}(L)} (pn) \text{ if } K \in \text{Rat}_p(Z^*)$$
$$< \lambda n \cdot ng_L(pn) \quad \square$$

Our first theorem allows us now to define a number of new families of languages.

**Definitions** : A language $L$ is said to be of **superior** (resp. **inferior**) **order** $f$ if and only if :

$$g_L < f \text{ (resp. } f < g_L\text{)}$$

A class of functions $F$ is said to be **extensive** (resp. **coextensive**) if and only if for all $f \in F$ and $pcN^+$ there exists $g \in F$ such that :

$$\lambda n \cdot nf(pn) < g \text{ (resp. } g < \lambda n \cdot nf([n/p])/n\text{)}.$$

For any class of functions $F$ we denote by $Less(F)$ the family of languages $L$ such that $g_L < f$ for some $f \in F$ and by $More(F)$ the family of languages $L$ such that $f < g_L$ for some $f \in F$.

Finally we call **anticone** a family of languages $L$ such that $L \subseteq L'$ and $\tau(L') = L$ (where $L'$ is any language and $\tau$ a rational transduction) imply $L' \subseteq L$, and recall that a **cone** is a family of languages closed by rational transduction.

It follows from theorem 1 :

**Corollary 1** : If $F$ is **extensive** Less ($F$) is a rational cone (and even a full AFL) ; if $F$ is **coextensive** More ($F$) is an anticone.

**Examples** : The family $Pol = \{\lambda n \cdot n^k | k \in \mathbb{N}^+\}$ is known to be extensive and the family $Exp = \{\lambda n \cdot 2^{qn} | q \in \mathbb{N}^+\}$ is known to be coextensive.

The languages in the rational cone Less(Pol) will be called **at most polynomial** and the languages in More(Pol) will be called **at least polynomial**.

A family of languages $L$ is **at most polynomial** if $Less(Pol) \subseteq L$.

After having studied the AFL operations of union, product, star, morphism, inverse morphism and intersection with a rational set, we now study the substitution.

Let us recall that the **syntactic substitution** $L_1 \circ L_2$ of $L_2$ into $L_1$ is defined if $L_1$ and $L_2$ are defined on two disjoint alphabets X and Y by :

$$L_1 \circ L_2 = (x_1 u_1 x_2 u_2 \cdots x_k u_k | x_1, \cdots, x_k \in X^*, x_1 x_2 \cdots x_k \in L_1, \text{ and } u_1, u_2, \cdots, u_k \in L_2)$$

**Lemma 7** : For all $n$ $g_{L_1 \circ L_2}(n) \le g_L(n) < g_{L_1}(n)$.

**Proof** : Let $K \in \text{Rat}_n(X \cup Y)^*$ be recognized by the automaton $<Q, q_0, Q_f, \lambda>.$
We define the rational sets $F_{q,q'}$ by $F_{q,q'} = \{u \in Y^* | q' \in Q, u(u)\}$. Consider now the language $K'$ defined by $x_1 x_2 \cdots x_k \in K'$ iff there exists a sequence of 2k

states $q_1, q_2, q'_1, \dots, q_k, q'_k$ such that

(1) $q_1 \in \lambda(x_1, q_0)$ and $q'_k \in Q_f$,

(2) $q_{i+1} \in \lambda(x_i, q'_i)$ and $K_{q_i, q'_i, nL'} \neq \emptyset$, for $i=1, \dots, k-1$.

One easily builds a nondeterministic automaton with n states recognizing $K'$.

Every word u in $K_n(LoL')$ is of the form $u = x_1 u_1 x_2 u_2 \cdots x_k u_k$ for some $x_1 \cdots x_k \in K'_n \cap LoL$ and there exists a sequence $q_1, q'_1, \dots, q_k, q'_k$ satisfying (1) and (2) such that $u_i \in K_{q_i, q'_i, nL'}$ for $i=1, \dots, k$. If we now take $x_1 \cdots x_k \in \min(K'_n \cap LoL)$ and $u_i \in \min(K_{q_i, q'_i, nL'})$ for $i=1, \dots, k$, we build a word u in $K_n(LoL')$ whose length is

$$|u| = \delta_{K', L} + \sum_{i=1}^{k} \delta_{K_{q_i, q'_i, L'}}$$

Thus $\delta_{K, LoL} \le |u| \le g_L(n)(1+g_L(n))$ and since this is true for all $K \in \text{Rat}_n((X \cup Y)^*)$, $g_{LoL}(n) \le g_L(n)(1+g_L(n))$. $\square$

A class of functions $F$ is closed under multiplication if for all $f, g \in F$ there exists $h \in F$ such that $\lambda n \cdot f(n) g(n) < h$.

**Theorem 2** : If $F$ is closed under multiplication and contains a function which grows faster than $\lambda n \cdot n$, then More (F) is a substitution closed full AFL.

*Proof* : Let us recall that if $L$ is a family of languages, an $L$-substitution $\sigma$ is a morphism of $X^*$ into $Y^*$ such that $\sigma(x) \in L \cap Y^*$ for all $x \in X$.

A family $L$ is closed under substitution if for all $L \in \mathcal{L}$ and $L$-substitution $\sigma$, $\sigma(L) \in L$.

The result follows from the fact that for every $L$-substitution $\sigma$, one can build a language $L_\sigma$ and a rational transduction $\tau$ such that $\tau(L_{L_\sigma}) = \sigma(L)$. We then apply preceding lemmas. $\square$

# PART II: Rational indices of context-free languages

In this section, we are interested in studying the orders of various classical subfamilies of the context-free languages. We first describe some classical languages.

Let $Z_2 = \{a_1, a_2\} u \{\bar{a}_1, \bar{a}_2\}$. We define on $Z_2^*$ the congruence $\equiv$ as being the congruence generated by $a_1 \bar{a}_1 \equiv a_2 \bar{a}_2 \equiv 1$. We denote by $D_2^* = \text{Dyck set over } Z_2$, i.e. the class of 1 modulo $\equiv$.

We shall also consider the language $D_1^* = D_2^* \cap \{a_1, \bar{a}_1\}^*$ and the symmetric language $S_2 = D_2^* \cap \{a_1, a_2\}^* \{\bar{a}_1, \bar{a}_2\}^*$.

Given a word $f$ in $Z_2^*$, we define $\delta(f) = |f|_{a_1} + |f|_{a_2} - (|f|_{\bar{a}_1} + |f|_{\bar{a}_2})$, where $|f|_x$ is the number of occurrences in $f$ of the letter $x$ of $Z_2$.

The height of $f$ is then the maximum of the $\delta(f')$ where $f'$ ranges over the left factors of $f$.

The width of $f$ is the largest number of non-empty left factor $h_1, h_2, \dots, h_k$ of $f$ such that $\delta(h_1) = \delta(h_2) = \dots = \delta(h_k)$.

We finally consider the language $d_2^*$ over $Z_2$ generated by the grammar : $S \to a_1 SS \bar{a}_1 + a_2 \bar{a}_2$.

**Proposition 1** : A context-free language $L$ is of superior order $\lambda n \cdot 2^{pn^2}$ for some $p$.

*Proof* : Given $L = L(G)$ and $R \in \text{Rat}_n(X^*)$, defined by $A = \langle Q, q_0, Q_f, \lambda \rangle$ one can construct a context-free grammar $\bar{G}$ the non-terminal of which are triples $(q, S, q')$ where $q, q' \in Q$ and $S$ is a non-terminal of $G$ such that $L(\bar{G}, (q, S, q')) = \{u \in X^* | u \in L(G, S) \text{ and } \lambda(q, u) = q'\}$.

The result follows immediately. $\square$

**Lemma 8** : The language $d_2^*$ is at least exponential.
**Proof** : Consider the following finite automaton $A_n$

<figure><img src="image_2.png" /></figure>

(where the state (n) both initial and final) ; we denote by $K_n$ the language recognized by $A_n$.

Obviously $d_2^1 \cap K_1 = \{a_2\bar{a}_2\}$; suppose now that $d_2^1 \cap K_{n-1} = \{u_{n-1}\}$, then we have $v \in d_2^1 \cap K_n$ iff $v = a_j v' \bar{a}_j$ and $v' \in K_{n-1} \cap d_2^1 d_2^1$.

If we observe that no word of $d_2^1$ can lead from a state q to a state q' where $q \neq q'$, we get that $v' = u_{n-1}u_{n-1}'$, so that $d_2^1 \cap K_n = \{a_1u_{n-1}u_{n-1}\bar{a}_1\} = \{u_n\}$.

Hence, $|u_n| = 2|u_{n-1}| + 2$ and $|u_1| = 2$, and we get $\delta_{K_n,L} = 2^{n+1} - 2 \le g_L(n+1)$. $\square$

**Theorem 3** : Any full generator of the family of context-free languages is at least exponential.

**Proof** : If L is a full generator then $d_2^1 = \tau(L)$. The result follows from theorem 1. $\square$

**Question** : Is it possible to improve the upper bound of proposition 1 ?

We now consider the linear and one-counter languages.

**Lemma 9** : The languages $S_2$ and $D_1^{*}$ are both at most polynomial.

**Proof** : 1. Consider the linear grammar $S \to a_1S\bar{a}_1 + a_2S\bar{a}_2 + I$ and an n-state finite automaton $A_n$. One gets a linear grammar generating $S_2nL(A_n)$ by the construction of proposition 1 which gives a linear grammar with $n^2$ non-terminals, so that $\delta_{L(A_n),S_2} \le 2n^2$. Hence $g_{S_2}(n) \le 2n^2$.

2. Let $KeRat_n(Z_1^*)$ and $ucMIN(D_1^* \cap K)$ be the height of u is less than $n^2$. If its height is greater than $n^2$, one can find a factorization $u = u_1u_2\cdots u_n2u'_n2\cdots u'_1$ such that :

$$ \delta(u_1u_2\cdots u_i) = \delta(u_1u_2\cdots u_n2u'_n2\cdots u'_{i+1}) = i. $$

and $\delta(v) \ge 0$ for all left factor of $u_{i+1}u_{i+1}'$.

Then one can choose two different indices i and j such that :

$$ w = u_1u_2\cdots u_iu_{j+1}\cdots u_n2u'_n2\cdots u'_{j+1}u_i'\cdots u'_1 \in D_1^{* \cap K} $$

so that u would not be in $MIN(D_1^{* \cap K})$. We can now prove that $|u| \le n^2(n+1)$. If it is not the case, then $u = u_0\cdots u_{n+1}$ for some $u_i \in X^*$ with $\delta(u_0) = \delta(u_0u_1) = \cdots = \delta(u_0\cdots u_n)$. Since K is defined by an n-state automaton, there exists $i < j$ such that $u' = u_0\cdots u_iu_{j+1}\cdots u_{n+1} \in K$ and $u' \in D_1^{* \cap K}$. Hence $ucMIN(D_1^{* \cap K})$.

Finally, $g_{D_1^*} (n) \le 2n^3$ for allmost all n. $\square$

**Proposition 2** : The rational cones Lin and Oct of linear and of one-counter languages respectively are at most polynomial.

**Proof** : Since Lin is generated by $S_2$ and Oct by $D_1^*$, the proposition is a direct consequence of theorem 1. $\square$

The substitution closure of Lin, is the full AFL Qrt of the quasi-rational languages.
The same construction performed with the one-counter gives the family Cit of iterated counter languages. Finally, we define Gre, the family of Greibach languages as being the substitution closure of Lin and Oct.

Using Proposition 2 and lemma 7, we get.

**Proposition 3** : The full AFL's Qrt, Cit and Gre are at most polynomial.

Let us now take an example showing that lemma 7 cannot be improved and showing how the superior order of quasi-rational languages behaves through substitution.
Consider $L_1 = \{a^n b^n | n \ge 1\}$ and the finite automaton $A_n$:

<figure><img src="image_3.png" /></figure>

Let $K_n$ be the language recognized by $A_n$ with $q$ as an initial state and $q'$ as final state and $2(n-1)$ more states which have not been drawn on the picture for simplicity. Quite easily $MIN(L_1 \cap K_n) = \{a^{n(n+1)} b^{n(n+1)}\}$, hence $\delta_{K_n, L_1} = 2n(n+1)$ whence $g_{L_1}(2n+1) \ge 2n(n+1)$ and we get $g_{L_1}(2n+2) \ge g_{L_1}(2n+1) \ge 2n(n+1)$ hence $g_{L_1} > \lambda n \cdot n^2$. Remark that, from the proof of lemma 8, we also know that $g_{L_1}(n) \le 2n^2$.

Using the same technique, we can easily show that $L_2 = \{x_2^p x_1^n \bar{x}_1^n x_2^p | n \in \mathbb{N}^+\}$ is such that $\lambda n \cdot n^2 < g_{L_2} < \lambda n \cdot n^2$.

Let now $L$ be the language obtained by the substitution $\sigma(a) = aL_2$ and $\sigma(b) = b$ applied to $L_1$. By lemma 7, we get $g_L < \lambda n \cdot n^4$.

We now describe a finite automaton $B_n$ with $3n$ states.

<figure><img src="image_4.png" /></figure>

We denote by $K'_n$ the language recognized by $B_n$ with $n$ as initial state and $\bar{n}$ as final state.

A routine proof can show that $u \le MIN(L \cap K'_n)$ where :
$$u = ax_2^2 \bar{x}_2^2 ax_2^2 w_2^2 \bar{w}_2^2 \cdots ax_2^{n(n+1)} w_2^{n(n+1)} \cdots \bar{w}_2^{n(n+1)}$$
and
$$w = x_1^n (n+1) - \bar{x}_1^n$$
The length of $u$ is greater than $n^4$.
Since $\delta_{K'_n, L} \le g_L(3n)$, we get $\exists_L > \lambda n \cdot n^4$.
**Remark 5**: The proof of lemma 8 shows that for any linear language $L$, $g_L(n) < \lambda n \cdot n^2$. The example given above can be extended to show that there exists for any p a language $L$ in $\text{Qrt}(p)$ such that :

$$ \lambda n \cdot n^{2p} < g_L < \lambda n \cdot n^{2p}. $$

$$ (\text{Recall that } \text{Qrt}(p) = \text{Qrt}(p-1)\sigma \text{ Lin and } \text{Qrt}(1) = \text{Lin, so that } \text{Qrt} = \bigcup_{p \ge 1} \text{Qrt}(p)). $$

A natural question is :

Is Gre the family of the context-free languages which are at most polynomial ?

The answer is no as shown below.

$$ \sigma(\bar{a}_1) = \bar{a}_1 \{\bar{a}_1, \bar{a}_2\}^* \text{ and } \sigma(\bar{a}_2) = \bar{a}_2 \{\bar{a}_1, \bar{a}_2\}^*. $$

We denote by $\Delta_2$ the language $\Delta_2 = \sigma(D_2^*)$. Recall that $\Delta_2$ is not a generator and that it does not belong to $\text{Gre}$ [4].

**Lemma 10**: The language $\Delta_2$ is at most polynomial.

**Proof**: With any word $u \in \Delta_2$, we can associate a word $u'$ in $D_2^*$ such that $u \in \sigma(u')$. It is then easy to see that if $u \in \text{MIN}(\Delta_2 \cap \text{K})$ with $K \in \text{Rat}_n(Z_2^*)$, then $u'$ must have an height bounded by $n^2$ and a width by $n$, so that $u'$ can be chosen with $|u'| \le 2n^2$. Clearly, when using the substitution $\sigma$, we cannot use any word in $\sigma(\bar{a}_i)$ the length of which is more than $n+1$, we get $u \in \text{MIN}(\Delta_2 \cap \text{K})$ implies $|u| \le 2n^2 + n^3$.

Whence $g_{\Delta_2} < \lambda n \cdot n^3$. □

Looking back at theorem 3, we then can state the

**Conjecture 1**: The largest full-subAFL of the full-AFL of context-free languages is the family of context-free languages which are at most polynomial.

We shall conclude by showing that a positive answer to conjecture 1 would give an answer to two other conjectures. Namely :

1) If conjecture 1 is true, the largest full-subAFL of the context-free languages is non principal (this is a conjecture of [5]).

The proof follows from :

**Proposition 4**: The family of the (context-free) languages which are at most polynomial is a non-principal full AFL.

**Proof**: It is enough to make sure that for infinitely many $k$, there exists a (context-free) language $L_k$ such that : $\lambda n \cdot n^k < g_{L_k} < \lambda n \cdot n^k$, which holds by Remark 5.

2) If conjecture 1 is true, then we have :

Any context-free language $L$ such that $<L>$ is an image of $L$ under a rational transfunction is a full generator of the full AFL of context-free languages. (This is similar to conjecture of [6]. Recall that $<L>$ denotes $\bigcup_{a \in \mathbb{A}} (a^n(Lb)^n/n \in \mathbb{N}^+)$ where $a,b$ are new letters).

The proof follows immediately from :

**Proposition 5**: If there is a rational transduction mapping $L$ on $<L>$, then $L$ is not at most polynomial.

**Proof**: With help of the example following proposition 2, one can prove $g_{<L>} (n) \ge n g_L(n)$ for any sufficiently large $n$, hence that $g_{<<L>>} (n) \ge n^2 g_L(n)$ for any sufficiently large $n$.

If $<L>$ is an image of $L$ under a rational transduction, the same holds for <<L>> , hence there exists an integer $p$ such that $g_{<<L>>} (n) \le pn g_L(pn)$ for any sufficiently large $n$ and we get : $n^2 g_L(n) \le pn g_L(pn)$.

Choosing then an integer $q$ such that $p \le 2^q$, we get $n g_L(n) \le 2^q g_L(2^q n)$ which implies for $n = 2^q \lambda$ :

$$ 2^q g_L (2^q \lambda) \le 2^q g_L (2^q + 1). $$
we can then ensure

$$2^{q^{\lambda}-1} g_L(2^{q^{\lambda}-1}) \le 2^{q^{\lambda}-1} g_L(2^{q^{\lambda}}) \le g_L(2^{q^{\lambda}+1})$$

for any sufficiently large q. Hence :

$$2^{q^{\lambda}-1} g_L(2^{q^{\lambda}-1}) \le g_L(2^{q^{\lambda}+1}) \quad \text{which gives}$$

$$g_L(2^{q^{\lambda}+1}) \ge 2^{q^{\lambda}-1.2^{q^{\lambda}-1} \dots 2^{q-1}} = 2^{q^{\lambda}(\lambda+1)-\lambda}$$

If L was at most polynomial, then, for some integer k, one would have :

$$2^{\frac{\lambda(\lambda+1)}{2}} - \lambda \le 2^{k(q^{\lambda}+1)} \quad \text{for all } \lambda \text{ which is clearly impossible. []}$$

## References :

[1] S. Eilenberg, "Automata, Languages, Machines", Vol.A, Academic Press, 1974

[2] M. Nivat, "Transductions des langages de Chomsky". Annales de l'Institut Fourier, Grenoble 18(1968) pp.339-456.

[3] L. Boasson, "Paires Itérantes et Langages algébriques", Thèse, Paris 1974.

[4] L. Boasson, "The inclusion of the substitution closure of Linear and One-counter languages in the largest sub-AFL of the family of Context-free languages is proper", Information Processing letters, 1974.

[5] S.A. Greibach, "Chain of full AFL's, Math. System Theory", 4(1970) pp. 231-242.

[6] L. Boasson, J.P. Crestin, M. Nivat, "Familles de langages translables et fermées par corchet", Acta Informatica 2(1973), 383-393.