18
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ 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? $\endgroup$
    – Evgenij Thorstensen
    Commented Oct 4, 2010 at 14:47
  • 1
    $\begingroup$ 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! $\endgroup$
    – Michaël Cadilhac
    Commented Oct 4, 2010 at 14:53
  • $\begingroup$ By the way, did you give it a try? $\endgroup$
    – Michaël Cadilhac
    Commented Oct 7, 2010 at 12:51
  • 5
    $\begingroup$ (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. $\endgroup$
    – Tsuyoshi Ito
    Commented Oct 9, 2010 at 21:55
  • 1
    $\begingroup$ 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. $\endgroup$
    – Michaël Cadilhac
    Commented Oct 10, 2010 at 3:14

1 Answer 1

Reset to default
9
$\begingroup$

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?

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you very much, this is indeed what I was searching for! $\endgroup$
    – Michaël Cadilhac
    Commented Nov 28, 2010 at 13:41
  • 1
    $\begingroup$ For the edit: Fantastic! Thanks for getting back there and completing this answer, this is great spirit! $\endgroup$
    – Michaël Cadilhac
    Commented Mar 6, 2017 at 23:25

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.