Consider the membership problem for a context-free language. An instance of this problem can be described as pair $(G,w)$, where $G$ is a context-free grammar and $w$ is a string.

Lets say I have a PRAM and I want it to decide in $\log^k n$ time and $n^c$ space complexity whether $w$ is in $L(G)$ ($c$ and $k$ are both constants) – that is, the complexity stays within Nick's class.

Is there such an algorithm? If so what would be an idea?

  • $\begingroup$ This article may contain helpful references and ideas. $\endgroup$ – Raphael May 20 '16 at 19:27
  • $\begingroup$ Alright, so the exact task can be rewritten like this: Assume MEM problem, problem which has CF grammar $G$ and word $w$ on input and asks if $w \in L(G)$. Next assume problem EMP, which has CFL G on the input and asks if there is a word $w$ s.t. $w \in L(G)$. Proof that $MEM \leq_{NC} EMP$. I just assumed that reduction can be done via solving the $MEM$ problem (with PRAM) and then return NON-empty / empty grammar $\endgroup$ – Smarty77 May 22 '16 at 9:08

It has been shown that CFL ⊆ NC² ⊆ NC [1] -- so yes, there is such an algorithm. I'm afraid the proof in that paper does not give you a PRAM algorithm, though.

  1. On uniform circuit complexity by W. Ruzzo (1981)
  • $\begingroup$ Yes I just found the same article as source from your previous response article. As you noted this proof is done via uniform boolean circuts and not via PRAM. $\endgroup$ – Smarty77 May 20 '16 at 19:57
  • 2
    $\begingroup$ Is this what the question's asking for? I interpret "$\mathrm{CFL}\subseteq\mathrm{NC}^2$" as meaning "every context-free language can be decided in $\mathrm{NC}^2$" but the question seems to be asking "Is the language $\{\langle G\rangle;w\mid G \text{ is a context-free grammar that generates }w\}$ in $\mathrm{NC}$?" $\endgroup$ – David Richerby May 21 '16 at 0:53
  • $\begingroup$ @DavidRicherby That's indeed a subtly different problem, but I daresay it should not be harder. $\endgroup$ – Raphael May 21 '16 at 1:12
  • $\begingroup$ @Raphael I have little intuition about context-free languages but it's much harder in the regular case: "Does this given NFA accept this input?" looks like it ought to be NL-complete (it's essentially about the existence of paths in digraphs). $\endgroup$ – David Richerby May 21 '16 at 3:04
  • 1
    $\begingroup$ @user2174310 If it's homework, I guess at least one of the following two approaches will work: 1) Adapt one of the standard CFG parsing algorithms. 2) Use an algorithmic technique presented in lecture, but in another context. $\endgroup$ – Raphael May 21 '16 at 10:16

The problem is not in NC unless P=NC. Jones and Laaser showed in "Complete Problems for Deterministic Polynomial Time" that the problem (therein called CFMEMBER) is P-complete. Interestingly, Ullman and Van Gelder showed in "Parallel Complexity of of logical query programs" that the same problem where the input CFG has no epsilon productions is in NC (Corollary 7.2).


Your Answer

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

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