Class Description

CFL: Context-Free Languages

Does not equal QCFL [MC00].

Contained in LOGCFL.

Strictly contains DCFL [Bra77] and indeed UCFL.

Linked From

1NAuxPDAp: One-Way NAuxPDAp

Defined in [Bra77], where it was also shown that 1NAuxPDAp strictly contains CFL and is strictly contained in LOGCFL. The class corresponds to the closure of CFL under one-way log-space reductions.

More about...


DCFL: Deterministic CFL

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.

More about...


QCFL: Quantum CFL

The class of decision problems recognized by quantum context-free languages, which are defined in [MC00]. The authors also showed that QCFL does not equal CFL.

More about...


UCFL: Unambiguous CFL

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.

More about...