<p>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.</p>

CC BY-SA 4.0
2023-04-28T14:23:56.613Z
Thanks so much for your answer!  Is this because there is an NL-complete problem in CFL?
Michael Wehar
CC BY-SA 4.0
2023-04-30T05:15:42.387Z
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!  :)
Michael Wehar
CC BY-SA 4.0
2023-04-30T05:18:45.407Z
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.
Michael Wehar
CC BY-SA 4.0
2023-04-28T00:26:28.083Z
2023-04-28T14:22:42.003Z
2023-04-28T14:22:42.003Z
user69092
<p><span class="math-container">$\mathrm{CFL}$</span> is the class of context-free languages.</p>
<blockquote>
<p><strong>Question</strong></p>
<p>Is <span class="math-container">$\mathrm{CFL}$</span> known to be solvable in <span class="math-container">$o(log^{2}(n))$</span> non-deterministic space? What about <span class="math-container">$\mathrm{DCFL}$</span>?</p>
</blockquote>

CC BY-SA 3.0
2018-01-14T18:18:10.733Z
Also see related question: https://cstheory.stackexchange.com/questions/14873/is-cfl-strictly-contained-in-nl
Michael Wehar
CC BY-SA 3.0
2018-01-16T19:25:29.010Z
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?
Thomas S
CC BY-SA 3.0
2018-01-16T20:12:27.643Z
Theorem 4 only shows the $\log^2 n$ bound?
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2018-01-16T20:18:47.010Z
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
CC BY-SA 3.0
2018-01-16T22:36:54.900Z
Also, thank you @Thomas for including the reference to the classic paper.  :)
Michael Wehar
CC BY-SA 3.0
2018-01-20T01:21:55.713Z
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: https://link.springer.com/chapter/10.1007/978-3-642-31644-9_13
Michael Wehar
CC BY-SA 4.0
2021-09-03T10:26:05.983Z
How about logcfl?
Turbo
CC BY-SA 4.0
2021-09-03T12:55:27.670Z
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)) )$?
Marzio De Biasi
<cc.complexity-theory><fl.formal-languages><automata-theory><context-free><logspace>
Is it known if $\mathrm{CFL} \subseteq\mathrm{ NSPACE}(o(log^2(n)))$?
Michael Wehar
# Is it known if $\mathrm{CFL} \subseteq\mathrm{ NSPACE}(o(log^2(n)))$?

(Asked by: username_0 on 2018-01-14)

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

**Tags:** cc.complexity-theory, fl.formal-languages, automata-theory, context-free, logspace

> **Comments:**
> **username_0**: Also see related question: https://cstheory.stackexchange.com/questions/14873/is-cfl-strictly-contained-in-nl  
> **username_1**: 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?  
> **username_2**: Theorem 4 only shows the $\log^2 n$ bound?  
> **username_0**: 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.  
> **username_0**: Also, thank you @Thomas for including the reference to the classic paper.  :)  
> **username_0**: 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: https://link.springer.com/chapter/10.1007/978-3-642-31644-9_13  
> **username_3**: How about logcfl?  
> **username_4**: 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)) )$?  

---

## 1 answers

### Answer by username_5 on 2023-04-28. Score: 1

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.

> **Comments:**
> **username_0**: Thanks so much for your answer!  Is this because there is an NL-complete problem in CFL?  
> **username_0**: 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!  :)  
> **username_0**: 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.  

---

