Class Description

CSL: Context Sensitive Languages

The class of languages generated by context-sensitive grammars.

Equals NSPACE(n) [Kur64].

Linked From

GCSL: Growing CSL

The class of languages generated by context-sensitive grammars in which the right-hand side of each transformation is either strictly longer than the left-hand side or the left-hand side consists of the start symbol.

Defined in [DW86] and shown to be contained in LOGCFL (and therefore in P among others).

Shown to be equivalent to Acyclic CSL in [Nie02].

More about...