Editing Context-sensitive language (section)

== Properties of context-sensitive languages ==

* The [[union (set theory)|union]], [[intersection (set theory)|intersection]], concatenation of two context-sensitive languages is context-sensitive, also the [[Kleene star#Kleene plus|Kleene plus]] of a context-sensitive language is context-sensitive.<ref>{{cite book|author=John E. Hopcroft|author2=Jeffrey D. Ullman|title=Introduction to Automata Theory, Languages, and Computation|url=https://archive.org/details/introductiontoau00hopc|url-access=registration|publisher=Addison-Wesley|year=1979|isbn=9780201029888}}; Exercise 9.10, p.230. In the 2000 edition, the chapter on context-sensitive languages has been omitted.</ref>
* The complement of a context-sensitive language is itself context-sensitive<ref>{{cite journal | last = Immerman | first = Neil | year = 1988 | title =Nondeterministic space is closed under complementation | journal = SIAM J. Comput. | issue = 5 | pages = 935–938 | doi = 10.1137/0217058 | volume = 17 | url=http://www.cs.umass.edu/~immerman/pub/space.pdf |archive-url=https://web.archive.org/web/20040625094023/http://www.cs.umass.edu/~immerman/pub/space.pdf |archive-date=2004-06-25 |url-status=live| citeseerx = 10.1.1.54.5941 }}</ref> a result known as the [[Immerman–Szelepcsényi theorem]].
* Membership of a string in a language defined by an arbitrary context-sensitive grammar, or by an arbitrary deterministic context-sensitive grammar, is a [[PSPACE-complete]] problem.