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].
The class of problems solvable by a nondeterministic multitape Turing machine in linear time. Defined in [BG69], where it was shown that Q equals the class of problems solvable by a nondeterministic multitape Turing machine in exactly n steps (as opposed to O(n) steps).
Contains GCSL.