Return to Question

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.

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.

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

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.