17

I'm interested in two questions regarding context-sensitive languages (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.

Hermann Gruber
  • 6,470
  • 1
  • 35
  • 58
Michaël Cadilhac
  • 3,946
  • 22
  • 39
  • 2
    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 Oct 04 '10 at 14:47
  • 1
    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 Oct 04 '10 at 14:53
  • By the way, did you give it a try? – Michaël Cadilhac Oct 07 '10 at 12:51
  • 4
    (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 Oct 09 '10 at 21:55
  • 1
    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 Oct 10 '10 at 03:14

1 Answers1

9

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?

Community
  • 1
Hermann Gruber
  • 6,470
  • 1
  • 35
  • 58