  The complexity class LOGCFL (resp., LOGDCFL) consists of all languages that
are many-one reducible to context-free (resp., deterministic context-free)
languages using logarithmic space. These complexity classes have been studied
over five decades in connection to parallel computation since they are located
between Nick's classes $\mathrm{NC}^1$ and $\mathrm{NC}^2$. In contrast, the
state complexity of nonuniform finite-automaton families was first discussed in
the 1970s and it has been extensively explored lately for various
finite-automata families. We extend this old subject to the stack-state
complexity (i.e., the total number of inner states plus simultaneously pushable
stack symbol series) of nonuniform families of various pushdown automata. We
introduce reasonable "parameterizations" of LOGCFL and LOGDCFL and apply them
as a technical tool to establish a close connection between the
LOGCFL$\subseteq$LOGDCFL/poly question and the polynomial stack-state
complexity of nonuniform families of two-way pushdown automata. We also discuss
the precise computational complexity of polynomial-size one-way pushdown
automata.
