# Prove that $L$ is closed under Kleene star iff $L=NL$

Prove that $L$ is closed under Kleene star iff $L=NL$

Hi,
I am trying to solve this exercise, but it is quiet difficult.
Of course first part is very easy:
Let assume that $L=NL$. Lets consider language $A\in L$. We show that also $A^*\in L$. It is easy because we can guess partition of word $w=w_1w_2..w_k$ and launch algorithm for each part. It is possible because $L=NL$ so being in class $L$ we can use guessing.

However, when we assume that $L$ is closed under Kleene star I am hopeless. Obviously, from assumption we know that $A\in L$ then also $A^*\in L$. Of course, we know that $L\subseteq NL$. However I must now show that $NL\subseteq L$ using assumption. This is hard for me.

• Some questions are supposed to be hard. – Yuval Filmus Aug 16 '17 at 19:31
• @YuvalFilmus Do you mean $A^* \in L \Rightarrow NL \subseteq L$ part? – fade2black Aug 16 '17 at 19:34
• Yes, that's the non-trivial part of this exercise. – Yuval Filmus Aug 16 '17 at 19:35

Let $A$ be the language consisting of the following words: $$(u,v)|\Sigma^*|(v,w),$$ where $u,v,w$ are numbers encoded in binary. This language is in $\mathsf{L}$.
Given a directed graph $G$, we can encode it as a list of edges in the following way: $$(x_1,y_1)(x_1,y_1)|(x_2,y_2)(x_2,y_2)|\cdots|(x_m,y_m)(x_m,y_m)$$ where $x_i,y_i$ are vertex numbers encoded in binary. Furthermore, this string, which we denote by $\langle G \rangle$, can be output by a logspace machine.
Suppose now that we are given two vertices $s,t$, and that there is an $s$-$t$ path of length $\ell$ of the form $(s,x),\ldots,(y,t)$ in $G$. Then I claim that for all $L \geq \ell$, $$(s,x)|\langle G \rangle^L|(y,t) \in A^*.$$ Conversely, if such a string belongs to $A^*$ then there is an $s$-$t$ path in $G$. In other words, $$\exists \text{s-t path in G} \longleftrightarrow (s,t) \in G \lor \exists x,y \text{ s.t. } (s,x)|\langle G \rangle^n|(y,t) \in A^*.$$
If we assume that $\mathsf{L}$ is closed under Kleene star then $A^* \in \mathsf{L}$, and so we can evaluate the right-hand side formula in logspace. Since $s$-$t$ reachability is $\mathsf{NL}$-complete, we deduce that $\mathsf{L}=\mathsf{NL}$.