<p>$\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.</p>

CC BY-SA 3.0
2012-05-03T05:08:36.620Z
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.
Charles Yu
CC BY-SA 3.0
2012-05-03T12:03:36.923Z
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.
Emil Jeřábek
CC BY-SA 3.0
2017-06-18T02:10:18.797Z
I understand you and all the above others now. Thanks,
Charles Yu
CC BY-SA 3.0
2012-04-30T11:52:56.727Z
2012-04-30T11:52:56.727Z
Emil Jeřábek
<p>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."</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2012-04-30T03:39:24.300Z
You should fold a shortened version of this into the question. It's not an answer.
Suresh Venkat
CC BY-SA 3.0
2012-05-01T06:05:19.613Z
@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.
Charles Yu
CC BY-SA 3.0
2012-05-01T20:23:35.520Z
Then provide the explanatory part in the question, and leave the answer part as the answer.
Suresh Venkat
CC BY-SA 3.0
2012-04-30T03:25:47.840Z
2012-04-30T03:25:47.840Z
Charles Yu
<p>wikipedia entry  says without reference that </p>

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

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

CC BY-SA 3.0
2012-04-28T04:14:28.280Z
What is the definition of "CSG is PSPACE-complete"?
Kaveh
CC BY-SA 3.0
2012-04-28T14:46:01.900Z
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.
vzn
CC BY-SA 3.0
2012-04-28T15:16:07.963Z
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
vzn
CC BY-SA 3.0
2012-04-28T23:24:32.137Z
QBF can be recognized with a suitable LBA.
sdcvvc
CC BY-SA 3.0
2012-04-30T03:31:20.783Z
Thx but see 3rd paragraph of my self answer below for your title question.
Charles Yu
<cc.complexity-theory><fl.formal-languages><grammars><parsing><pspace>
are there fixed context sensitive grammars which are PSPACE complete?
Charles Yu
# are there fixed context sensitive grammars which are PSPACE complete?

(Asked by: username_0 on 2012-04-28)

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?

**Tags:** cc.complexity-theory, fl.formal-languages, grammars, parsing, pspace
> **Comments:**
> **username_1**: What is the definition of "CSG is PSPACE-complete"?  
> **username_2**: 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.  
> **username_2**: 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  
> **username_3**: QBF can be recognized with a suitable LBA.  
> **username_0**: Thx but see 3rd paragraph of my self answer below for your title question.  

---

## 2 answers

### Answer by username_4 on 2012-04-30. Score: 7 | Accepted answer

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

> **Comments:**
> **username_0**: 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.  
> **username_4**: 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.  
> **username_0**: I understand you and all the above others now. Thanks,  

---

### Answer by username_0 on 2012-04-30. Score: -1

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.

> **Comments:**
> **username_5**: You should fold a shortened version of this into the question. It's not an answer.  
> **username_0**: @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.  
> **username_5**: Then provide the explanatory part in the question, and leave the answer part as the answer.  

---

