9
$\begingroup$

$\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}$?

$\endgroup$
8
  • $\begingroup$ Also see related question: cstheory.stackexchange.com/questions/14873/… $\endgroup$ Jan 14, 2018 at 18:18
  • $\begingroup$ 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? $\endgroup$
    – Thomas S
    Jan 16, 2018 at 19:25
  • $\begingroup$ Theorem 4 only shows the $\log^2 n$ bound? $\endgroup$ Jan 16, 2018 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, 2018 at 20:18
  • 1
    $\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, 2021 at 12:55

1 Answer 1

1
$\begingroup$

It is not known whether CFL is contained in space o(log^2(n)). If CFL were contained in space o(log^2(n)), then NL would also be contained in space o(log^2(n)). The question whether NL is contained in space o(log^2(n)) is surprisingly still an open question in complexity theory.

$\endgroup$
3
  • $\begingroup$ Thanks so much for your answer! Is this because there is an NL-complete problem in CFL? $\endgroup$ Apr 28, 2023 at 14:23
  • $\begingroup$ Oh, maybe this follows because NL is a subset of logCFL and CFL in space o(log^2(n)) would imply that logCFL in o(log^2(n)). Cool! Thank you again for pointing this out! :) $\endgroup$ Apr 30, 2023 at 5:15
  • 1
    $\begingroup$ Ah, I see. My original question had to do with nspace, not dspace. This is great, but doesn't seem to lead to conclusions about the original question. $\endgroup$ Apr 30, 2023 at 5:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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