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

$CFL$ is the class of context-free languages.

Question

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

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?

• Theorem 4 only shows the $\log^2 n$ bound? – Hsien-Chih Chang 張顯之 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. – Michael Wehar Jan 16 '18 at 20:18
• Also, thank you @Thomas for including the reference to the classic paper. :) – Michael Wehar Jan 16 '18 at 22:36