# Complexity of classes of languages and operators

Philippe Flajolet, Jean-Marc Steyaert

► To cite this version:

Philippe Flajolet, Jean-Marc Steyaert. Complexity of classes of languages and operators. [Research Report] IRIA-RR-092, IRIA. 1974, pp.13. hal-04715985

HAL Id: hal-04715985

https://inria.hal.science/hal-04715985v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

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

Distributed under a Creative Commons Attribution 4.0 International License
RIA
laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
78150 - Le Chesnay
Tél. 954.90.20

laboratoire de recherche
en informatique
et automatique

Complexity of
classes of languages
and operators

P. Flajolet, J.M. Steyaert

Rapport de Recherche n° 92

Novembre 1974
COMPLEXITY OF CLASSES OF LANGUAGES AND OPERATORS

P. Flajolet, J.M. Steyaert

**Abstract :**

We study the way nonerasing homomorphism and star operation operate on time and space bounded classes.

**Résumé :**

On étudie la manière dont les opérateurs d'homomorphisme continu et d'opération étoile opèrent sur les classes de complexité en temps et en mémoire.
The results presented in this paper are related to the following question : how does the complexity of classes of languages ( AFL, semi-AFL ) relate to that of their generators ? Our purpose is to derive a notion of complexity of operators such as non-erasing homomorphism and star operation.

Our results extend previous ones by Savitch [10] , Hartmanis [9] , Sudborough [12], Shamir-Beeri [11], Book [1] and Book-Greibach-Wegbreit [3].

In the first part, we show that, due to a property of the symmetrical language over two letters - $S_2 = \{ ww^R / w \in \{ a,b \}^* \} -$, $S_2^* -$ the star closure of $S_2$ - is recognisable in deterministic log-space. This property may underlie the unpublished result of Pratt mentioned in Cook [6] that $S_2^*$ is linear time recognisable by a random access machine. On the other hand, a modification of Sudborough's construction [12] shows that the semi-AFL$^†$ generated by the star closure of linear context-free languages contains languages which are recognisable in non deterministic log-space and furthermore are complete for this class. Since other semi-AFL operations do not modify space complexity of languages, we can interpret this result in the following way : homomorphism transforms the star of some linear language which is deterministic log-space recognisable into non deterministic log-space complete languages.

In the second part, we strengthen these results : we construct a linear language which is nSPACE ( log ) complete. This language is the simplest of all known complete languages, since Sudborough's language is in the AFL generated by the *star closure* of linear languages. In other words, the problem of the inclusion nSPACE ( log ) ⊂ dSPACE ( log ) is equivalent to the deterministic log-space recognition of linear languages i-e to the inclusion Lin ⊂ dSPACE ( log ). Here Lin, the class of linear languages, is actually a very simple subclass of nSPACE ( log ).

In the third part, we show that semi-AFL operations lead to NP-complete languages when applied to very simple languages - repetition languages - which are deterministic log-space recognisable and therefore belong to P.

In the last part we compare star operation properties to those of non-erasing
homomorphisms which have been studied in previous parts.

In each case, we show our results to be, in a sense, optimal.

<footnote>† A semi-AFL ( SAFL for short ) is closed under union, intersection with regular sets, non erasing homomorphism and inverse homomorphism.</footnote>
1. The language $S_2^*$ and the AFL it generates

Let $S_2$ be the symmetrical language over two letters generated by axiom S and productions $S \to aSa + bSb + \lambda$:

$S_2 = \{ ww^R / w \in \{a,b\}^* \}$. The deterministic log-space recognition algorithm for $S_2^*$ is based on the following property of $S_2$:

**Lemma 1:** If $W = XY \in S_2$ and $X \in S_2$, then $Y \in S_2^*$.

**Proof:** Assume that $X = xx^R$ and $W = ww^R$. The proof is done by induction on the value of the ratio $\frac{|X|}{|W|}$ (see fig 1).

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

<figure><img src="image_3.png" /><figcaption>fig. 1</figcaption></figure>
$$
(\alpha) \quad \text{Basic step} = \frac{|X|}{|W|} \le \frac{1}{2}
$$

Let $v$ be such that $w = xx^R v$ ; then

$$
W = xx^R v ( xx^R v )^R = xx^R v v^R xx^R ; \text{ hence}
$$

$$
Y = v v^{R} x x^{R} \in S_{2}^{*}
$$

$$
(\beta) \quad \text{Induction step} = \text{Assume that the property holds for all } X \text{ and } W \text{ s.t. } \frac{|X|}{|W|} \le \frac{n}{n+1};
$$

$$
\text{we now prove that it holds equally for all } X \text{ and } W \text{ s.t. } \frac{|X|}{|W|} \le \frac{n+1}{n+2}
$$

$$
\text{Let } X \text{ and } W \text{ be such that } W = X Y \text{ for some } Y, X = xx^R, W = ww^R \text{ and} \\
\frac{1}{2} < \frac{|\dot{X}|}{|W|} \le \frac{n+1}{n+2}.
$$

$$
\text{Since } |X| > \frac{|W|}{2} \text{ we have } X = wu \text{ for some } u. \text{ Then, } W = wu^R = X Y = wuY ;
$$

$$
\text{hence } w^R = uY \text{ and } w = Y^R u^R ; \text{ hence } X = Y^R u^R u \text{ and } X^R = u^R uY. \text{ Let } U = u^R u \\
\text{and consider the ratio } \frac{|U|}{|X|} :
$$

$$
|U| = |X| - |Y| ; \text{ but } |Y| = |W| - |X| ;
$$

$$
\text{hence } |U| = 2|X| - |W| \text{ and}
$$

$$
\frac{|U|}{|X|} = 2 - \frac{|W|}{|X|} ;
$$

$$
\text{since} \quad \frac{|X|}{|W|} \le \frac{n+1}{n+1} \quad \text{we conclude that}
$$

$$
\frac{|U|}{|X|} \le 2 - \frac{n+2}{n+1} = \frac{n}{n+1} . \text{ We can thus apply the induction hypothesis}
$$

that $Y$ belongs to $S_2^*$, which proves the induction step.

$$
(\gamma) \quad \text{The case } \frac{|X|}{|W|} = 1 \text{ is trivial, which completes the proof of lemma 1. } \Box
$$

**Remark :** The above proof shows furthermore that if a palindrome W can be divided by another palindrome , then W can be divided by a palindrome of length less than $\frac{|W|}{2}$.
From lemma 1 we derive

**Lemma 2** : Let W = X Y where X is the smallest nonnull left factor of W belonging to S₂; then W ∈ S₂* iff Y ∈ S₂*.

**Proof** : The condition is sufficient by definition. To prove it necessary, let W = W₁ ... W_S where all the Wᵢ's belong to S₂; by hypothesis |X| ≤ |W₁| ; by lemma 1 we get W₁ = X T and T belongs to S₂* ; hence Y = T W₂ ... W_S is in S₂* . □
We can now prove the following result :

**Theorem 1** : S₂* can be recognised by a deterministic Turing machine in log-space.

**Proof** : Let us first remark that S₂* is obviously in nSPACE( log ) : it is easy to design a non-deterministic multihead finite automaton which recognises S₂* by guessing successive subwords of the input and checking each guess to be a palindrome. The membership of S₂* in dSPACE( log ) relies upon lemmas 1 and 2 ; more precisely, we use lemma 2 to design the following recursive recognition procedure :

**procedure** starpal 1(W) : find the smallest non-null left factor of W which is a palindrome - say X ; if no such X exists then reject ; otherwise let Y be the remaining part of W ( W = XY ) : if Y = λ then accept, otherwise call starpal 1(Y).

Let W = x₁... xₚ   xᵢ ∈ { a,b } . For k,ℓ   1≤k≤ℓ≤p = |W| , W( k,ℓ )
denotes the subword xₖxₖ+₁... xℓ of W. The above recursive procedure is then equi-
valent to the following algorithm :

**procedure** starpal 2(W);
  k ← 1; ℓ ← 2;
  **TRY** : if W(k,ℓ) ∈ S₂ then goto **SUCCESS**
                      else goto **FAILURE**;
  **SUCCESS** : if ℓ = |W| then result ← YFS;
                if ℓ = |W|-1 then result ← NO;
                k ← ℓ+1; ℓ ← k+1; goto **TRY**;
  **FAILURE** : if ℓ = |W| or ℓ = |W|-1 then result ← NO;
                      ℓ ← ℓ+2; goto **TRY**;

The test W( k,ℓ ) ∈ S₂ can be performed using two new counters p and q.
Hence the procedure starpal 2 can be implemented using a finite number of counters
each of them being bounded above by the length of the input W. Therefore, S₂* can
be recognised in log-space on a deterministic Turing machine. []
Although $S_2^*$ belongs to dSPACE( log ) we show that applying semi-AFL operations on $S_2^*$ enables us to get nSPACE( log ) complete sets.

**Proposition 1**: SAFL($S_2^*$) contains nSPACE( log ) complete languages.

**Proof**: (outlined):

It is clear that Sudborough's language $L_p^\dagger$ [ 12 ] belongs to the AFL generated by the *marked star closure of the symmetrical language with central marker* :

$$K = \{ \$ w_1 \subset w_1^R \$ w_2 \$ \dots \$ w_p \subset w_p^R \$ / p \in N \ \& \ w_i \in \{ a, b \}^* \}$$

Let $S_5$ be the symmetrical language over $\Sigma_5 = \{ a, b, \alpha, \beta, \gamma \}$; we first show that SAFL($S_5^*$) contains nSPACE( log ) complete sets. Let $P_5 \subset \Sigma_R^*$ be the regular set defined by : $P_5 = ( \alpha\alpha\alpha( a+b )^*\beta\beta( a+b )^*\alpha\gamma\gamma )^* ; S_5 \cap R_5$ is exactly the set of all words of the kind :

(E) $\alpha\alpha\alpha u_1 \beta\beta u_1^R \alpha\gamma\gamma\alpha\alpha\alpha u_2 \beta\beta u_2^R \alpha\gamma\gamma \dots \alpha\alpha\alpha u_n \beta\beta u_n^R \alpha\gamma\gamma$, which is very close to K. Hence, modulo the representation of markers, SAFL($S_5^*$) contains a language trivially equivalent to Sudborough's $L_p$.

In order to extend this property to SAFL($S_2^*$), we define a language $R_2$ obtained from $R_5$ by a binary encoding of a,b,α,β,γ which preserves property (E).

For instance, one can choose the following one :

a : 01

b : 10

α : 00000

β : 10001

γ : 11111 .□

$\dagger$ $L_p$ is the set of all strings of the form

$[ x_1^1 * y_1^2 * y_1^2 * \dots * y_1^{n_1} ] \dots [ x_t^1 * y_t^1 * y_t^2 * \dots * y_t^{n_t} ] u_1^* \dots u_r^*$

where $x_i, y_i^j, u_i \in \{ a, b \}^*$

and satisfy the property : there exists a $p \ge 1$

and integers $i_1, i_2, \dots, i_p$ s.t. :

(1) $1 = i_1 < i_2 < \dots < i_p$

(2) $\forall k ( 1 < k \le p ) \exists l ( 1 < l < n_i \le k \le l ) x_i^R = y_i^l$

(3) $\exists l ( 1 \le l < n_i ) y_i^l \in \{ u_1^R, \dots, u_r^R \}$
## 2. Space complexity of linear languages

In this section we first show that linear languages can be recognised by non-deterministic two head finite automata; we then show that, although they form a very simple subclass of nSPACE( log ), nevertheless they contain complete sets for this class.

**Proposition 2 :** Lin is nSPACE( log )

**proof :** Assume the linear language is given by a linear grammar ( rules are of the form A → uBv. ). The non-deterministic two head finite automaton is designed in such a way that if T is a derivation tree for the input word,

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

then :

- it first guesses the "middle" of the input, i.e, puts head 1 on the last symbol of $u_{n+1}$ and head 2 on the first one of $v_{n+1}$

- then moves head 1 backward and head 2 forward storing ( non-deterministically ) $u_{n+1}^R$ and $v_{n+1}$ in its finite control. Then it finds $A_n$ in the grammar and resumes the tape scanning guessing $u_n^R$ and $v_n$ ; it then finds $A_{n-1}$ that $A_{n-1} \to u_n A_n v_n$ etc...

- the automaton accepts its input if it finds the axiom while the heads scan both ends of the input.

Due to equivalence between ( non-deterministic ) multihead finite automata and ( non-deterministic ) log space recognition, we obtain the weaker result :

Lin is nSPACE( log ). □
In the following it will be convenient to introduce variants of Sudborough's $L_p$.

**Definition** : Let $M_2$ be the set of strings of the form $u_1 \in \{a,b\}^*$ which satisfy :

(1) $u_i \in \{a,b\}^*$

(2) $\exists i_1 = 0 < i_2 < \dots < i_p = n \quad \text{s.t.}$
$$ \forall k<p \quad u_{2i_k+1} = u_2^{i_k} $$

**Lemma 3** : $M_2$ is nSPACE( log ) complete

**Proof** : ( straightforward ) $M_2$ is a mere variant of $L_p$. Blocks of the type

$[ x_i * y_i^1 * y_i^2 * \dots * y_i^{n_i} ]$ in $L_p$ are represented in $M_2$ by the strings :
$x_i \in \{ y_i^1, y_i^2, \dots, y_i^{n_i} \}$.

This transformation can obviously be performed in log-space. ☐

One can now avoid parity constraints occuring in the definition of $M_2$.

**Definition** : Let $N_3$ be the set of strings of the kind $u_1 \in \{a,b,\alpha\}^*$

(1) $u_i \in \{a,b,\alpha\}^*$

(2) $\exists i_1 = 0 < i_2 < \dots < i_p = m \quad \text{s.t.}$

$\forall k<p \quad u_{i_k+1}^R = u_{i_k+1}^R$

- let $N_2$ be the language defined similarly with $u_i \in \{a,b\}^*$.

**Lemma 4** : $N_2$ is nSPACE( log ) complete.

**Proof** : $N_2$ and $N_3$ belong trivially to nSPACE( log ). To prove them complete, we first show that $M_2$ reduces to $N_3$ in log-space : the function $\rho$ ensuring the reduction is defined by :

$$ \rho(u_1 \in \{a,b,\alpha\}^* \cup \{u_2 \in \{a,b,\alpha\}^* \mid u_2 \text{ is a binary encoding of } \{a,b,\alpha\}\}) = u_1 \in \{a,b,\alpha\}^* \cup \{u_2 \in \{a,b,\alpha\}^* \mid u_2 \text{ is a binary encoding of } \{a,b,\alpha\}\} $$

Hence $N_3$ is nSPACE( log ) complete. $N_3$ reduces to $N_2$ via a trivial binary encoding of $\{a,b,\alpha\}$ into $\{a,b\}^2$, which completes the proof. ☐

We now prove that a specific linear language is nSPACE( log ) complete.
**Definition**: Let L be the language over alphabet { a,b,¢, $ } defined by the following grammar, S being the axiom :

$$
\left\{
\begin{array}{l}
S \rightarrow Sa + Sb + S\¢ + T\¢ \\
T \rightarrow aTa + bTb + \¢U\¢ + \$ \\
U \rightarrow aU + bU + \¢U + \¢V \\
V \rightarrow aVa + bVb + \¢S\¢ + \$
\end{array}
\right.
$$

When generating a word in L the grammar operates as follows :

(1) In state S an arbitrary sequence of words in { a,b }* separated by ¢'s is generated on the right ; state T is then entered while a ¢ is generated. At the end of such a phase the generated word is of the form

w¢ + ¢uk¢ ... u2 ¢ u1 ¢ w'

(2) In state T two words in { a,b }* are generated which are mirror images of one another

w¢u_{k+1}¢ + ¢u_{k+1}^{P}¢ + ¢u_{k}¢ ... ¢u_{1}¢w'

(3) State U is similar to S, but the sequence is generated on the left

w¢u_{k+1}¢ + u_{k+2}¢ ... + u_{l}¢ + ¢u_{k+1}^{R}¢ + u_{k}¢ + u_{k}¢ ... ¢u_{1}¢w'

(4) State V is the analogue of state T.

w¢u_{k+1}¢ + u_{k+2}¢ ... + u_{l+1}¢ + ¢u_{l+1}^{R}¢ + u_{k}¢ ... ¢u_{1}¢ w'

L is a linear language and thus belongs to nSPACE( log ). Intuitively
what makes its recognition difficult, is that one has to distinguish pairs of
mirror words from sequences generated in states S and U.

More precisely we can state

**Theorem 2**: The language L which is linear is nSPACE (log) complete

**Proof**: Let $\sigma: \{a,b,\¢\}^* \rightarrow \{a,b,\¢,\$,\}$\}^*$ be defined by: $\sigma(w) = w\$\tau(w)$,
where $(w_1 \¢ w_2 \dots \¢ w_n) = w_n \¢ \dots \¢ w_1$. $\sigma$ is log-space computable and reduces
$N_2$ to L as shown below :

$$
N_2 : w_1 \¢ w_2 \dots w_i \¢ w_{i+1} \dots \¢ w_j \¢ w_{j+1} \dots \¢ w_n \arrow[r] \arrow[d]_{R} & \{ w_1 \¢ w_2 \dots w_i \¢ w_{i+1} \dots \¢ w_j \¢ w_{j+1} \dots \¢ w_n \arrow[r] \arrow[d]_{R} & \{ w_1 \¢ w_2 \dots w_i \¢ w_{i+1} \dots \¢ w_j \¢ w_{j+1} \dots \¢ w_n \arrow[r] \arrow[d]_{R} & \dots \arrow[r] \arrow[d]_{R} & \dots \arrow[r] \arrow[d]_{R} & \dots \arrow[r] \arrow[d]_{R} \}
$$

L :

$$
w_1 \dots w_i \dot{\otimes} w_{i+1} \dots w_j \dot{\otimes} w_{j+1} \dots w_n \$ w_n \dots w_{j+1} \dot{\otimes} w_j \dots w_{i+1} \dot{\otimes} w_i \dots w_1
$$
**Corollary 1 :** (i) Lin contains nSPACE( log ) - complete languages

(ii) Any linear language is log-space reducible to L.

Thus we have shown that L is the more complex linear language with
respect to space ( cf. Greibach [8] for similar properties of context-free
languages ).

3. AFL's generated by repetition languages.

In this section we study semi-AFL's generated by the following languages,
which we call repetition languages :

$$
A = \{ w \in W \mid \dots \in W \} = \{ (w \in W)^n / w \in \{ 0,1 \}^*, n \in \mathbb{N} \}
$$

$$
B = \{ w \in W^R \mid \dots \in W^R \} = \{ (w \in W^R)^n / w \in \{ 0,1 \}^*, n \in \mathbb{N} \}
$$

$$
C = \{ w \in W \mid \dots \in W \} = \{ (w \in W)^n \cup (w \in W^R)^n / w \in \{0,1\}^*, n \in \mathbb{N} \}
$$

These languages have quite simple structures : they are deterministic
log-space recognisable ; A is recognisable by a one way two head finite automaton,
B is the intersection of two context-free languages and C is the intersection of
two linear languages. However applying semi-AFL operations yields
NP- complete languages.

**Theorem 3** : (i) There exist a homomorphism g, a nonerasing homomorphism h and a regular set R, such that h(g⁻¹(A)∩R) is NP-complete.

(ii) Similar properties holds for B and C.

**Proof** : We just show part (i) of the theorem, the proof for (ii) being essentially the same

Cook [7] has shown SCNF(2) to be NP-complete where SCNF(2) is the satisfiability problem for boolean expressions in conjunctive normal form, where variables are indexed by integers in binary notation. Shamir-Beeri [11] recently observed that NP-completeness remains true for SCNF(1) i.e. when indices are in unary notation; they then proved that context-free programmed grammars generate NP-complete languages. We go one step further and show that it is not even necessary to name variables.

Let $F = \bigwedge_{j=1}^{n} C_j$ be a boolean function in conjunctive normal form, and let $\text{var}(F)$ be the set of variables involved in $F$ (these variables may be indexed in binary notation, for instance) ; choose now an arbitrary order on $\text{var}(F)$ with the only restriction that is easily computable from $F$ ( for instance, take lexicographical order on binary notations ) ; hence,
var(F) = { p₁, p₂, ..., pₘ }. We can now represent a clause Cⱼ of F by a string

$$ \text{where :} \quad \begin{array}{c} \alpha_j^1 \quad \alpha_j^2 \quad \alpha_j^m \\ P_1 \quad P_2 \quad \dots \quad P_m \end{array} \\ \alpha_j = \begin{cases} \text{if } p_i \text{ occurs negatively in } C_j \\ \sim \text{ if } p_i \text{ does not occur in } C_j \\ \text{if } p_i \text{ occurs positively in } C_j \end{cases} $$

The boolean function F is then uniquely determined by the sequence of all $\alpha_j^i$'s. We define SCNF(θ) to be the set of strings $\alpha_1^1 \alpha_1^2 \dots \alpha_1^m \dots \alpha_n^1 \alpha_n^2 \dots \alpha_n^m$ which represent a satisfiable boolean expression. SCNF(0) is clearly NP-complete.

We now show that g,h,P exist such that SCNF(0) = h(g⁻¹(A) ∩ R).

(α) g is an homomorphism from

$$ \Sigma_7 = \{ (0,+), (0,\emptyset), (0,-), (1,+), (1,\emptyset), (1,-), \emptyset \} $$

into $\Sigma_3 = \{ 0,1,\emptyset \}$ defined by :

$$ g(\emptyset) = \emptyset $$

$$ g(0,+)=g(0,\emptyset)=g(0,-)=0 $$

$$ g(1,+)=g(1,\emptyset)=g(1,-)=1 $$

Given a word $a = (w\¢)^n$ in A, $g^{-1}(a)$ is the set of representations of all boolean expressions in conjunctive normal form with n clauses and $|w|$ variables which are valued by the string w. Hence $g^{-1}(A)$ represents the set of all (not necessarily satisfiable) boolean expressions together with a given valuation of their variables.

(β) R is a regular set defined by

$$ R = ((\Sigma_7^* \cdot ((0,-) + (1,+))). \Sigma_7^* \cdot \emptyset)^* $$

R represents the set of all valued boolean expressions in the sense of (α), such that each clause is satisfied, but clauses may have different lengths and the *valuations may differ* from one clause to another.

$g^{-1}(A) \cap R$ then represents the set of boolean expressions with a *given valuation* repeated throughout which satisfies all the clauses.

(γ) Finally the non-erasing homomorphism h is defined by :

$$ h(\emptyset) = \emptyset $$

$$ h(0,-) = h(1,-) = - $$

$$ h(0,\emptyset) = h(1,\emptyset) = \emptyset $$

$$ h(0,+)=h(1,+)=+ $$
In other words, h erases the valuation assigned to a formula in $g^{-1}(A) \cap R$. □

Let 1FA2 be the class of deterministic one way two head finite automata, Q be the class of images of intersections of context-free languages under nonerasing homomorphism, [2] and BNP be the similar class for linear languages [5]. We get as a corollary :

**Corollary 2 :** (i) SAFL ( 1FA2 ) contains an NP-complete language

(ii) ( Book ) Q contains an NP-complete language

(iii) ( Book-Nivat ) BNP contains an NP-complete language.

**Proof :**

(i) A ∈ 1FA2

(ii) $B = C_1 \cap C_2$ where

$$
C_1 = \{ w_1 \in w_1^R \in w_2 \in w_2^R \in \dots \in w_i \in \{0,1\}^* \}
$$

$$
C_2 = \{ w_0 \in w_1 \in w_1^R \in w_2 \in w_2^R \in \dots \in w_i \in \{0,1\}^* \}
$$

and Q is an AFL

(iii) $C = L_1 \quad L_2$ where

$$
L_1 = \{ w_1 \in \dots \in w_m \in \dots \in w_1^R \in \dots \in w_m^R / w_i \in \{0,1\}^*, m \in \mathbb{N} \}
$$

$$
L_2 = \{ w_1 \in \dots \in w_m \in \dots \in w_{m+1} \in w_m^R \dots \in w_2^R / w_i \in \{0,1\}^*, m \in \mathbb{N} \}
$$

and BNP is a semi-AFL. □

**Remark :** We have shown that applying nonerasing homomorphism to log-space-hence polynomial time recognisable langages, yields NP-complete languages. These results are optimal in the sense that applying nonerasing homomorphism to P gives only languages in NP. When dealing with space, we do not know if application of nonerasing homomorphisms to dSPACE( log ) leads to languages outside nSPACE( log ) ; a positive answer would solve one of the basic problems in logical complexity, that is the link between time and space for non-deterministic machines. Finally, we restricted ourselves to nonerasing homomorphisms since erasing homomorphism applied to classes like $nSPACE( \log )$ or $1FA2$ generates the whole class of r.e. sets.

**4. Properties of star operation**

We previously saw that the star operation on $S_2$ yields a language of the same space complexity ; we show below that star operation takes us at most from a deterministic space class to the non deterministic one defined by the same bound ; Furthermore star operation may yield complete languages. This constrasts with time classes that are not much affected by star operation : P being, for instance, closed under this operation.
**Proposition 3** : Let $f$ be an increasing function between $\log n$ and $n$; let $g$ be a space-honest increasing function greater than $n$.

Then : for any language $L$

$$ (i) \quad L \in \mathrm{dSPACE}(f) \implies L^* \in \mathrm{nSPACE}(l) $$

$$ (ii) \quad L \in \mathrm{dSPACE}(g) \implies L^* \in \mathrm{dSPACE}(g) $$

**Proof** : (straightforward) For less-than-linear bounds one can parse $L^*$ non-deterministically by guessing a decomposition of the input into subwords which belong to $L$. For more-than-linear bounds, one checks deterministically all decompositions of the input which require linear space. $\Box$

**Proposition 4** : There exists $H \in \mathrm{dSPACE}(\log)$ such $H^*$ is $\mathrm{nSPACE}(\log)$-complete.

**Proof** : Language $N_2$ has been proven to be $\mathrm{nSPACE}(\log)$-complete. Notice now that $N_2$ is the star closure of the following linear language :

$$ H = \{ w_0 \in \mathrm{w}_1 \in \dots \in \mathrm{w}_m \in \mathrm{w}_c^R \mid w_i \in \{a,b\}^* \}. $$

Moreover $H$ is clearly in $\mathrm{dSPACE}(\log)$. $\Box$

Finally we can prove for time classes the following :

**Proposition 5** : Let $t$ a time-honest increasing function then

$$ L \in \mathrm{dTIME}(t) \rightarrow L^* \in \mathrm{dTIME}(u) \text{ where } u(n) = n^3 \cdot t(n). $$

**Proof** : We use a generalisation of Younger's algorithm for context-free parsing.

Let $w$ be an input word; we build inductively a boolean matrix $A = (a_{ij})$

$$ \text{such that : } a_{ij} = \begin{cases} \text{true} & \text{iff } w(i,j) \in L^* \end{cases}. $$

The $a_{ij}$'s are computed successively according to increasing values of $j-i$.

$$ a_{ii} = \begin{cases} \text{true} & \text{iff } w(i,i) \in L \\ \text{false} & \text{otherwise} \end{cases}. $$

$$ a_{ij} = \begin{cases} \text{true} & \text{iff } \begin{cases} \text{either } w(i,j) \in L \\ \text{or } \exists k \ i \le k \le j \ (a_{ik} \land a_{kj}) \end{cases} \\ \text{false} & \text{otherwise} \end{cases}. $$

The result is given by the value of $a_{in}$.

The algorithm requires $n^3$ computations of the parsing algorithm for $L$ on words whose length is less than or equal to that of $w$; other computations on the indices and the matrix entries can clearly be performed in time $n^3$. $\Box$

**Corollary 3** : (Book) $P$ is closed under star operation.
References :

[1] Book "On languages accepted in polynomial time". Harvard University report. ( 1972 ).

[2] Book-Greibach "Quasi-real-time languages". Math. Systems Theory 4. ( 1970 ) 97-111.

[3] Book-Greibach-Weigbreit "Time and tape bounded Turing acceptors and AFLs". JCSS 4,6 ( 1970 ) 606-621.

[4] Book-Nivat "Private communication"

[5] Book-Nivat-Paterson "Reversal bounded acceptors and intersections of linear languages". To appear in SIAM Journal of Computing ( 1974 ).

[6] Cook "Linear time simulation of deterministic two-way pushdown automata". Proceedings of IFIP conference ( 1971 ).

[7] Cook "The complexity of theorem-proving procedures". Proc. of the 3rd ACM Symp. on Th. of Comp. ( 1971 ).

[8] Greibach "The hardest context-free language". SIAM Journal of Computing 4, ( 1973 ) 304-310.

[9] Hartmanis "On non determinacy in simple computing devices". Acta Informatica 1, ( 1972 ) 336-344.

[10] Savitch "Relationships between non deterministic and deterministic tape complexities". JCSS 4,2 ( 1970 ) 177-192.

[11] Shamir-Beeri "Checking stacks and Context-free programmed grammars accept p-complete languages" in Automata Languages and Programming 2nd Colloquium. Saarbrücken ( 1974 ) Springer Verlag.

[12] Sudborough "On tape bounded complexity classes and multi-head finite automata". Proc. of 14th IEEE Symposium on Switching and Automata Theory ( 1973 ),