The class of languages accepted by deterministic pushdown automata.
Defined in [GG66], where it was also shown that DCFL is strictly contained in CFL, contained in UCFL, and strictly contains REG. The inclusion in UCFL is also strict.
Contained in LOGCFL.
Strictly contains DCFL [Bra77] and indeed UCFL.
(Named in honor of Stephen Cook.)
The class of decision problems solvable by a Turing machine that simultaneously uses polynomial time and polylogarithmic space.
Note that SC might be smaller than P ∩ polyL, since for the latter, it suffices to have two separate algorithms: one polynomial-time and the other polylogarithmic-space.
Deterministic context-free languages (DCFLs) can be recognized in SC [Coo79].
SC contains RL and BPL [Nis92].
SC equals DTISP(poly,polylog) by definition.
The class of context-free languages which can be represented by grammars where each word in the language has exactly one leftmost derivation.
Strictly contains Deterministic CFL. Strictly contained in CFL.