<p>To answer your first question, a reducibility fitting your needs is log-lin-reducibility, which is logspace reducibility with the additional constraint that the size of the output string of the reduction is at most linear in the size of the input. If I remember correctly, the membership problem for context-sensitive grammars (or, if you like, linearly bounded automata) is the canonical CSL-complete problem w.r.t. log-lin reducibility.</p>

<p>On the applied side, the universality problem of (ordinary) regular expressions over binary alphabet, is CSL-complete w.r.t. log-lin-reducibility. The notion and the completeness result are found in  Albert R. Meyer and Larry J. Stockmeyer (SWAT 1972) also: Stockmeyer (PhD thesis, MIT 1974). For further background and similar results in that area, see also the recent survey by Holzer and Kutrib (DLT 2010).</p>

<p><strong>EDIT (2017/03/06):</strong> Regarding your second question, the accepted answer to the question below cites a paper by Rounds (1973), which constructs a one-way nested stack automaton recognizing SAT. While SAT will not qualify as a "natural" CSL, it might be worth to search the literature for other examples of one-way nested stack automata or indexed grammars.</p>

<p><a href="https://cstheory.stackexchange.com/questions/9982/context-sensitive-grammar-for-sat">Context-sensitive grammar for SAT?</a></p>

CC BY-SA 3.0
2017-03-06T23:25:46.367Z
For the edit: Fantastic!  Thanks for getting back there and completing this answer, this is great spirit!
Michaël Cadilhac
CC BY-SA 2.5
2010-11-28T13:41:28.933Z
Thank you very much, this is indeed what I was searching for!
Michaël Cadilhac
CC BY-SA 3.0
2010-11-25T22:28:59.890Z
2017-03-06T20:06:10.160Z
2017-04-13T12:32:28.053Z
Hermann Gruber
<p>I'm interested in two questions regarding <a href="http://en.wikipedia.org/wiki/Context-sensitive_language" rel="noreferrer">context-sensitive languages</a> (CSL) and completeness:</p>

<ol>
<li> Is there a notion of completeness for CSL, and which languages are complete?</li>
<li> Are there natural CSL that are NP-complete?</li>
</ol>

<p>For 2., I can certainly think of natural NP-complete languages that are CSL (as CSL is equal to NSPACE[$n$], SAT is a CSL), but I'm searching for the other way around, i.e., a context-sensitive <em>grammar</em> describing an NP-complete language.</p>

CC BY-SA 2.5
2010-10-04T14:47:36.150Z
Let's see if I understand (2) correctly: Would it be sufficient to write a context-sensitive grammar that generates all valid 3SAT instances over a fixed alphabet of connectives and SAT variables?
Evgenij Thorstensen
CC BY-SA 2.5
2010-10-04T14:53:58.187Z
Well, I would not have added SAT variables as part of the alphabet (a binary encoding of their indices is good enough), but that would certainly answer my second point!
Michaël Cadilhac
CC BY-SA 2.5
2010-10-07T12:51:36.310Z
By the way, did you give it a try?
Michaël Cadilhac
CC BY-SA 2.5
2010-10-09T21:55:01.267Z
(1) As you mentioned, it is possible to write down a CSG for 3SAT, but that sounds similar to writing down a complete description of a Turing machine for the maximum-flow problem (or any specific language in P); I would not expect that it will give any insight on complexity theory.  (But hey, if it turns out otherwise, I will be happy to hear it.)  (2) Generally, the notion of context-sensitive grammars and the notion of NP-completeness do not go well together because the set of context-sensitive languages is not closed under polynomial-time reductions.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-10T03:14:34.153Z
Thanks for that comment Tsuyoshi.  Indeed, a grammar for 3SAT is probably not what I'm searching for, but I went with the same reaction as yours: if it is somewhat easy/natural, I'd be interested.  For your (2), one of my aim is the following: say I have a class of CS languages closed by logspace-reduction, and I want to show that my class does not (or is unlikely to) contain NP-complete problems, I would only have to show that the specific NP-complete CS language is not in my class, which could be easier if the language is naturally CS.
Michaël Cadilhac
<np-hardness><fl.formal-languages><space-bounded>
Completeness and Context-Sensitive Languages.
Michaël Cadilhac
# Completeness and Context-Sensitive Languages.

(Asked by: username_0 on 2010-10-03)

I'm interested in two questions regarding [context-sensitive languages](http://en.wikipedia.org/wiki/Context-sensitive_language) (CSL) and completeness:

1. Is there a notion of completeness for CSL, and which languages are complete?
2. Are there natural CSL that are NP-complete?

For 2., I can certainly think of natural NP-complete languages that are CSL (as CSL is equal to NSPACE[$n$], SAT is a CSL), but I'm searching for the other way around, i.e., a context-sensitive *grammar* describing an NP-complete language.

**Tags:** np-hardness, fl.formal-languages, space-bounded

> **Comments:**
> **username_1**: Let's see if I understand (2) correctly: Would it be sufficient to write a context-sensitive grammar that generates all valid 3SAT instances over a fixed alphabet of connectives and SAT variables?  
> **username_0**: Well, I would not have added SAT variables as part of the alphabet (a binary encoding of their indices is good enough), but that would certainly answer my second point!  
> **username_0**: By the way, did you give it a try?  
> **username_2**: (1) As you mentioned, it is possible to write down a CSG for 3SAT, but that sounds similar to writing down a complete description of a Turing machine for the maximum-flow problem (or any specific language in P); I would not expect that it will give any insight on complexity theory.  (But hey, if it turns out otherwise, I will be happy to hear it.)  (2) Generally, the notion of context-sensitive grammars and the notion of NP-completeness do not go well together because the set of context-sensitive languages is not closed under polynomial-time reductions.  
> **username_0**: Thanks for that comment Tsuyoshi.  Indeed, a grammar for 3SAT is probably not what I'm searching for, but I went with the same reaction as yours: if it is somewhat easy/natural, I'd be interested.  For your (2), one of my aim is the following: say I have a class of CS languages closed by logspace-reduction, and I want to show that my class does not (or is unlikely to) contain NP-complete problems, I would only have to show that the specific NP-complete CS language is not in my class, which could be easier if the language is naturally CS.  

---

## 1 answers

### Answer by username_3 on 2010-11-25. Score: 9 | Accepted answer

To answer your first question, a reducibility fitting your needs is log-lin-reducibility, which is logspace reducibility with the additional constraint that the size of the output string of the reduction is at most linear in the size of the input. If I remember correctly, the membership problem for context-sensitive grammars (or, if you like, linearly bounded automata) is the canonical CSL-complete problem w.r.t. log-lin reducibility.

On the applied side, the universality problem of (ordinary) regular expressions over binary alphabet, is CSL-complete w.r.t. log-lin-reducibility. The notion and the completeness result are found in Albert R. Meyer and Larry J. Stockmeyer (SWAT 1972) also: Stockmeyer (PhD thesis, MIT 1974). For further background and similar results in that area, see also the recent survey by Holzer and Kutrib (DLT 2010).

**EDIT (2017/03/06):** Regarding your second question, the accepted answer to the question below cites a paper by Rounds (1973), which constructs a one-way nested stack automaton recognizing SAT. While SAT will not qualify as a "natural" CSL, it might be worth to search the literature for other examples of one-way nested stack automata or indexed grammars.

[Context-sensitive grammar for SAT?](https://cstheory.stackexchange.com/questions/9982/context-sensitive-grammar-for-sat)

> **Comments:**
> **username_0**: Thank you very much, this is indeed what I was searching for!  
> **username_0**: For the edit: Fantastic!  Thanks for getting back there and completing this answer, this is great spirit!  

---

