14
$\begingroup$

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}$.

Improve this question
$\endgroup$
8
  • 7
    $\begingroup$ 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))$. $\endgroup$
    – Max
    Dec 27, 2012 at 13:00
  • 2
    $\begingroup$ 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}$ which contains $\mathsf{NL}$. $\endgroup$
    – Kaveh
    Dec 27, 2012 at 14:16
  • 1
    $\begingroup$ @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) $\endgroup$
    – Vanessa
    Dec 29, 2012 at 13:20
  • 1
    $\begingroup$ @Squark I meant to write NL-complete, not NP. $\endgroup$
    – cineel
    Jan 1, 2013 at 5:39
  • 1
    $\begingroup$ Also, what about deterministic logspace? $\endgroup$
    – Ryan Dougherty
    May 1, 2015 at 23:14

1 Answer 1

Reset to default
-2
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Apr 27 at 13:02
  • $\begingroup$ Perhaps this point is not rigorously proven. But it seems to me that the details can be easily provided. $\endgroup$
    – user69092
    Apr 27 at 17:20
  • $\begingroup$ 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 $\endgroup$
    – user69092
    Apr 27 at 20:14
  • $\begingroup$ 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. :) $\endgroup$
    – Michael Wehar
    Apr 30 at 5:26

Your Answer

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

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