2
$\begingroup$

wikipedia entry says without reference that

"There are even some context-sensitive grammars whose fixed grammar recognition problem is PSPACE-complete."

This is stronger than saying that CSG is PSPACE-complete. But is this proved? where are the references?

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ What is the definition of "CSG is PSPACE-complete"? $\endgroup$
    – Kaveh
    Commented Apr 28, 2012 at 4:14
  • 1
    $\begingroup$ there is a semifamous problem of meyer/stockmeyer called "recognition of regular languages with exponentiation" that is proven PSpace complete. presumably the algorithm can be implemented on a LBA, linear bounded automaton ("most" built in theoretical CS constructions can-- am not aware of counterexamples except through diagonalization, is anyone else? maybe will ask that question here). LBAs recognize exactly the CSLs, context sensitive languages (same class as CSGs). regular language proof can be found in Intro to automata theory by hopcroft & ullman or also online in chee yaps book. $\endgroup$
    – vzn
    Commented Apr 28, 2012 at 14:46
  • 1
    $\begingroup$ correction its the fullness problem for regular languages with exp. ie whether the RL with exp. is equiv to all strings in the alphabet. have also seen a scanned version of this meyer/stockmeyer paper online, will dig it up if someone wants it $\endgroup$
    – vzn
    Commented Apr 28, 2012 at 15:16
  • 2
    $\begingroup$ QBF can be recognized with a suitable LBA. $\endgroup$
    – sdcvvc
    Commented Apr 28, 2012 at 23:24
  • $\begingroup$ Thx but see 3rd paragraph of my self answer below for your title question. $\endgroup$
    – Charles Yu
    Commented Apr 30, 2012 at 3:31

2 Answers 2

Reset to default
7
$\begingroup$

$\mathrm{CSL}=\mathrm{NSPACE}(O(n))$. Thus, take your favourite PSPACE-complete problem. If it is decidable in $\mathrm{NSPACE}(O(n))$ (for example, QBF is), you are done. Otherwise, introduce a polynomial amount of padding to make it so.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Emil, thanks but with all respect I think you misunderstood my question. Your answer explains why CSL/CSG is PSPACE complete. But that is not being asked! Read my explanatory comments below for why. $\endgroup$
    – Charles Yu
    Commented May 3, 2012 at 5:08
  • 1
    $\begingroup$ According to the terminology in your comment below, my answer shows that there is a fixed grammar G' (and in fact, lots of them) whose FCSG is PSPACE-complete. If that's not your question, then I have no idea what is. $\endgroup$
    – Emil Jeřábek
    Commented May 3, 2012 at 12:03
  • $\begingroup$ I understand you and all the above others now. Thanks, $\endgroup$
    – Charles Yu
    Commented Jun 18, 2017 at 2:10
-1
$\begingroup$

To draw continued attention, here are some explanatory comments, with a tentative proof based on the idea of universal CSG. The original quote (in my original post) is from wikipedia entry: Context-sensitive grammar, requote here: "There are even some context-sensitive grammars whose fixed grammar recognition problem is PSPACE-complete."

The statement that the word recognition problem for CSG is PSPACE-complete and the statement that the same kind of problem for some fixed grammar in CSG is PSPACE compelte are different! The former is sometimes called universal recognition problem for CSG, and the latter, well, may be called just fixed CSG grammar recognition problem. Let's refer to the two problems as UCSG and FCSG respectively.

The instances of UCSG are pairs of (G,x) where G can be any CSG, and x can be any strings; whereas those of FCSG for a fixed grammar G', are pairs of (G',x) where G' is fixed, and x can be any string. Thus to say UCSG is PSPACE complete, it means that there is a polynomial time transformation T such that for any decision problem Q in PSPACE, there is pair (G,x)=T(Q) such that the answer to (G,x) is the answer to Q; Whereas to say FCSG for a fixed CSG G' is PSPACE complete, it means that there is a polynomial time transformation T' such that for any decision problem Q in PSPACE, there is string x, such that (G',x)=T'(Q) is the equivalent problem to Q.

When the original author states that FCSG is PSPACE complete without giving a reference, he (she) may think that it is kind of obvious or its importance does not justify more detail. But I think a reference or certain hints are valuable here, assuming it is right.

Along this line of thinking, my tentative proof plan for FCSG being PSPACE complete is the following: Let H be such a special grammar in CSG such that H accepts x if and only if x=u#v where u is the coding (by some coding funciton) of arbitrary grammar G(u) in CSG and G(u) accepts v. Since the condition of H is fulfillable by a LBA (or not so?), by the equivalence of LBA and CSG, such H exists; and any ICSG for such a H is PSPACE complete. Since this H can simulate any other CSG, we may call it universal CSG.

Are there proofs along this line already, where, or this purported proof plan has flaws? If the idea of universal CSG is essentially right, we may continue asking what other classes have their own universal instances.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ You should fold a shortened version of this into the question. It's not an answer. $\endgroup$
    – Suresh Venkat
    Commented Apr 30, 2012 at 3:39
  • $\begingroup$ @suresh I am not sure how to follow your suggestion, as I posted the question, First, I think explanatory points are in real needs, as my question was not adequately understood as seen in the first comments and answer. Second, my point in second paragraph from bottom is literally a self answer based on my later thoughts, regardless of whether it is right. $\endgroup$
    – Charles Yu
    Commented May 1, 2012 at 6:05
  • 1
    $\begingroup$ Then provide the explanatory part in the question, and leave the answer part as the answer. $\endgroup$
    – Suresh Venkat
    Commented May 1, 2012 at 20:23

Your Answer

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

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