Class Description

NAuxPDA^p: Nondeterministic Auxiliary Pushdown Automata

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

Equals LOGCFL [Sud78].

Linked From

1NAuxPDA^p: One-Way NAuxPDA^p

Defined in [Bra77], where it was also shown that 1NAuxPDA^p 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...

AuxPDA: Auxiliary Pushdown Automata

Equivalent to NAuxPDA^p without the running-time restriction.

Equals P [Coo71b].

More about...