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

$\endgroup$
  • 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 '12 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 '12 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$ – Squark Dec 29 '12 at 13:20
  • 1
    $\begingroup$ @Squark I meant to write NL-complete, not NP. $\endgroup$ – cineel Jan 1 '13 at 5:39
  • 1
    $\begingroup$ Also, what about deterministic logspace? $\endgroup$ – Ryan May 1 '15 at 23:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.