Class Description

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

Linked From

Q: Quasi-Realtime Languages

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.

More about...