$\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}$?
$\begingroup$
$\endgroup$
8
asked Jan 14, 2018 at 18:17
-
$\begingroup$ Also see related question: cstheory.stackexchange.com/questions/14873/… $\endgroup$– Michael WeharJan 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 SJan 16, 2018 at 19:25
-
$\begingroup$ Theorem 4 only shows the $\log^2 n$ bound? $\endgroup$– Hsien-Chih Chang 張顯之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$– Michael WeharJan 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$– Marzio De BiasiSep 3, 2021 at 12:55
|
Show 3 more comments
1 Answer
$\begingroup$
$\endgroup$
3
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.
-
$\begingroup$ Thanks so much for your answer! Is this because there is an NL-complete problem in CFL? $\endgroup$ Apr 28 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 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 at 5:18