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


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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.