Class Description

LOGCFL: Logarithmically Reducible to CFL

The class of decision problems reducible in L to the problem of deciding membership in a context-free language.

Equals uniform SAC1 [Ven91]: LOGCFL is the class of decision problems solvable by a uniform family of AC1 circuits, in which no AND gate has fan-in exceeding 2 (see e.g. [Joh90], p. 137).

LOGCFL is closed under complement [BCD+89]. For more on LOGCFL from the descriptive complexity viewpoint, including completeness results under FO reductions, see [LMSV01].

Contains NL [Sud78], and also the problem of recognizing graphs of bounded tree-width [Wan94].

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


CFL: Context-Free Languages

Does not equal QCFL [MC00].

Contained in LOGCFL.

Strictly contains DCFL [Bra77] and indeed UCFL.

More about...


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


NAuxPDAp: Nondeterministic Auxiliary Pushdown Automata

The class of problems solvable by nondeterministic logarithmic-space and polynomial-time Turing machines with auxiliary pushdown.

Equals LOGCFL [Sud78].

More about...


NL: Nondeterministic Logarithmic-Space

NL is to L as NP is to P. Not known whether a particular relation (equality or inequality) between P and NP implies the same relation between L and NL.

In a breakthrough result, was shown to equal coNL [Imm88] [Sze87]. (Though contrast to mNL.)

Is contained in LOGCFL [Sud78], as well as NC2.

Is contained in UL/poly [RA00].

Deciding whether a bipartite graph has a perfect matching is hard for NL [KUW86].

NL can be defined in a logical formalism as SO(krom) and also as FO(tc), reachability in directed graph is NL-Complete under FO-reduction.

More about...


SAC0: Semi-Unbounded-Fanin AC0

See SAC for definition.

Not closed under complement [BCD+89].

Not contained in ⊕SAC0 [K23].

SAC1: Semi-Unbounded-Fanin AC1

See SAC for definition.

Equals LOGCFL/poly [Ven91].

Contained in ⊕SAC1 [GW96].

More about...