<p>The language Squares is contained in NL and this is not a context-free language. The question is whether CFL is contained in NL. If CFL is not contained in NL, then NL is not equal to P. There is recent-work by Montoya-Flum claiming that CFL is not contained in NL and that NL is different to P. It could then happen that the second big problem of complexity theory was solved to thanks to the analysis of grammar classes that are supposed to be not amenable for complexity theory.</p>

CC BY-SA 4.0
2023-04-27T13:02:28.133Z
FWIW, the claim ultimately boils down to point (c) on p. 6, whose short hand-waving “proof” is no proof at all, it’s just a string of several more unsubstantiated claims.
Emil Jeřábek
CC BY-SA 4.0
2023-04-27T17:20:21.150Z
Perhaps this point is not rigorously proven. But it seems to me that the details can be easily provided.
user69092
CC BY-SA 4.0
2023-04-27T20:14:44.023Z
I can feel certain animosity in this forum.  Emil could ask for details, but he decided to thrown out the whole proof. Is point c, page 6, the crucial flaw? No, problem. Hsia and Yeh used roughly the same sequence to prove that the pebble hierarchy is strict (see Hsia, Yeh, Marker Automata). The languages in this alternative sequence are context-free languages. Thus, problem solved. Why did I receive two negative votes? I am providing a reference that seems to answer the question in full: CFL is not strictly contained in NL, to the contrary NL is strictly contained in logCFL
user69092
CC BY-SA 4.0
2023-04-30T05:26:47.357Z
Idk anything about this proposed proof, but I'm excited to hear that people are actively thinking about this!  I hope to look into it more, although it might take me some time.  :)
Michael Wehar
CC BY-SA 4.0
2023-04-27T10:34:52.213Z
2023-04-27T10:34:52.213Z
user69092
<p>We know that $\mathsf{REG}=\mathsf{NSPACE}(O(1))$ and $\mathsf{CSL}=\mathsf{NSPACE}(O(n))$. </p>

<p>What is the relation of $\mathsf{CFL}$ and $\mathsf{NSPACE}(O(\log n))=\mathsf{NL}$?<br>
Is $\mathsf{CFL}$ a proper subset of $\mathsf{NL}$?</p>

<p>Note that $\{0^k1^k2^k \mid 0 \leq k \}$ is not context-free, but in $\mathsf{NL}$.</p>

CC BY-SA 3.0
2012-12-27T13:00:56.533Z
I have found a 1977 paper (Log Space Recognition and Translation of Parenthesis Languages by Nancy Lynch) with states that this is an open problem (and that $\mathsf{CFL} \subset \mathsf{L}$ implies $\mathsf{L} = \mathsf{NL}$). Hopcroft and Ullman showed that $\mathsf{CFL} \subset \mathsf{DSPACE}(O(\log^2 n))$.
Max
CC BY-SA 3.0
2012-12-27T14:16:16.013Z
Btw, the language you have is not just in $\mathsf{NL}$ but in $\mathsf{L}$. Generally grammar classes are not that interesting from complexity theory point of view because they are not closed. The more natural complexity class to study is [$\mathsf{LogCFL}$](http://en.wikipedia.org/wiki/LOGCFL) which contains $\mathsf{NL}$.
Kaveh
CC BY-SA 3.0
2012-12-29T09:53:00.240Z
Does anybody know an NP-complete context-free language?
cineel
CC BY-SA 3.0
2012-12-29T13:20:43.597Z
@cineel : CFL is in LOGCFL which is in AC1 which is in NC which is in P. So it is definitely disjoint with NPC (if you believe P is not NP)
Vanessa
CC BY-SA 3.0
2013-01-01T05:39:56.770Z
@Squark I meant to write NL-complete, not NP.
cineel
CC BY-SA 3.0
2013-01-03T07:48:56.920Z
@cineel, you may want to post that as a separate question.
Kaveh
CC BY-SA 3.0
2015-05-01T20:38:50.243Z
understand the question but (afaik) this is not really a strictly std/ correct use of the notation to say/ abbreviate that language classes like CFL or CSL are themselves a class like complexity classes L or NL etc, they are not in the same class. what you mean is _complexity class of recognition of a language class..._
vzn
CC BY-SA 3.0
2015-05-01T23:14:42.783Z
Also, what about deterministic logspace?
Ryan Dougherty
<cc.complexity-theory><fl.formal-languages><space-bounded><grammars>
Is CFL strictly contained in NL?
cineel
# Is CFL strictly contained in NL?

(Asked by: username_0 on 2012-12-27)

We know that $\mathsf{REG}=\mathsf{NSPACE}(O(1))$ and $\mathsf{CSL}=\mathsf{NSPACE}(O(n))$.

What is the relation of $\mathsf{CFL}$ and $\mathsf{NSPACE}(O(\log n))=\mathsf{NL}$?  
Is $\mathsf{CFL}$ a proper subset of $\mathsf{NL}$?

Note that $\{0^k1^k2^k \mid 0 \leq k \}$ is not context-free, but in $\mathsf{NL}$.

**Tags:** cc.complexity-theory, fl.formal-languages, space-bounded, grammars
> **Comments:**
> **username_1**: I have found a 1977 paper (Log Space Recognition and Translation of Parenthesis Languages by Nancy Lynch) with states that this is an open problem (and that $\mathsf{CFL} \subset \mathsf{L}$ implies $\mathsf{L} = \mathsf{NL}$). Hopcroft and Ullman showed that $\mathsf{CFL} \subset \mathsf{DSPACE}(O(\log^2 n))$.  
> **username_2**: Btw, the language you have is not just in $\mathsf{NL}$ but in $\mathsf{L}$. Generally grammar classes are not that interesting from complexity theory point of view because they are not closed. The more natural complexity class to study is [$\mathsf{LogCFL}$](http://en.wikipedia.org/wiki/LOGCFL) which contains $\mathsf{NL}$.  
> **username_0**: Does anybody know an NP-complete context-free language?  
> **username_3**: @cineel : CFL is in LOGCFL which is in AC1 which is in NC which is in P. So it is definitely disjoint with NPC (if you believe P is not NP)  
> **username_0**: @Squark I meant to write NL-complete, not NP.  
> **username_2**: @cineel, you may want to post that as a separate question.  
> **username_4**: understand the question but (afaik) this is not really a strictly std/ correct use of the notation to say/ abbreviate that language classes like CFL or CSL are themselves a class like complexity classes L or NL etc, they are not in the same class. what you mean is _complexity class of recognition of a language class..._  
> **username_5**: Also, what about deterministic logspace?  

---

## 1 answers

### Answer by username_6 on 2023-04-27. Score: -2

The language Squares is contained in NL and this is not a context-free language. The question is whether CFL is contained in NL. If CFL is not contained in NL, then NL is not equal to P. There is recent-work by Montoya-Flum claiming that CFL is not contained in NL and that NL is different to P. It could then happen that the second big problem of complexity theory was solved to thanks to the analysis of grammar classes that are supposed to be not amenable for complexity theory.

> **Comments:**
> **username_7**: FWIW, the claim ultimately boils down to point (c) on p. 6, whose short hand-waving “proof” is no proof at all, it’s just a string of several more unsubstantiated claims.  
> **username_6**: Perhaps this point is not rigorously proven. But it seems to me that the details can be easily provided.  
> **username_6**: I can feel certain animosity in this forum.  Emil could ask for details, but he decided to thrown out the whole proof. Is point c, page 6, the crucial flaw? No, problem. Hsia and Yeh used roughly the same sequence to prove that the pebble hierarchy is strict (see Hsia, Yeh, Marker Automata). The languages in this alternative sequence are context-free languages. Thus, problem solved. Why did I receive two negative votes? I am providing a reference that seems to answer the question in full: CFL is not strictly contained in NL, to the contrary NL is strictly contained in logCFL  
> **username_8**: Idk anything about this proposed proof, but I'm excited to hear that people are actively thinking about this!  I hope to look into it more, although it might take me some time.  :)  

---

