Class Description

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

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


AuxPDA: Auxiliary Pushdown Automata

Equivalent to NAuxPDAp without the running-time restriction.

Equals P [Coo71b].

More about...