# 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, 2018 at 18:18
• Yes. This is Theorem 4 in the following paper. Philip M. Lewis II, Richard Edwin Stearns, Juris Hartmanis: Memory bounds for recognition of context-free and context-sensitive languages. SWCT (FOCS) 1965: 191-202. Edit: I am sorry. My answer is not helpful. I missed the "small o". Stupid... I am not sure what to do. Delete the answer? Jan 16, 2018 at 19:25
• Theorem 4 only shows the $\log^2 n$ bound? Jan 16, 2018 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, 2018 at 20:18
• 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, 2021 at 12:55