# Is it known if $\mathrm{CFL} \subseteq\mathrm{ NSPACE}(o(log^2(n)))$?

$$\mathrm{CFL}$$ is the class of context-free languages.

Question

Is $$\mathrm{CFL}$$ known to be solvable in $$o(log^{2}(n))$$ non-deterministic space? What about $$\mathrm{DCFL}$$?

• Also see related question: cstheory.stackexchange.com/questions/14873/… Jan 14 '18 at 18:18
• Comment about DCFL's being solvable in less space was removed as it only applied to a certain class of DCFL's. See here for more info: link.springer.com/chapter/10.1007/978-3-642-31644-9_13 Jan 20 '18 at 1:21
– Mr.
Sep 3 at 10:26
• If $L$ is CF then $L = \varphi( R \cap Dick_k)$ where R is regular, Dick_k is the Dyck language over k symbols and $\varphi$ is an homomorphism. Didn't think about it too much, but $R \cap Dick_k$ should be solvable in $DSPACE(\log(n))$. So a parallel more general problem could be: given $L \in CFL$ and $\varphi$ homomorphism, if $L$ is recognized in $NSPACE(o(\log^2(n)))$, can $\varphi^{-1}(L)$ be recognized in $NSPACE( o(\log^2(n)) )$? Sep 3 at 12:55

• Theorem 4 only shows the $\log^2 n$ bound? Jan 16 '18 at 20:12
• Thank you @Hsien-ChihChang張顯之 ! Yes, I might not have made my question clear enough. I was asking if we can do better than $\log^2(n)$ space. I updated the question changing "less than" to little oh to hopefully clarify. Jan 16 '18 at 20:18