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


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

  • $\begingroup$ Also see related question: cstheory.stackexchange.com/questions/14873/… $\endgroup$ Jan 14 '18 at 18:18
  • $\begingroup$ 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 $\endgroup$ Jan 20 '18 at 1:21
  • $\begingroup$ How about logcfl? $\endgroup$
    – Mr.
    Sep 3 at 10:26
  • $\begingroup$ 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)) )$? $\endgroup$ Sep 3 at 12:55

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?

  • 4
    $\begingroup$ Theorem 4 only shows the $\log^2 n$ bound? $\endgroup$ 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$ Jan 16 '18 at 20:18
  • $\begingroup$ Also, thank you @Thomas for including the reference to the classic paper. :) $\endgroup$ 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.