  Existing definitions of the relativizations of \NCOne, \L\ and \NL\ do not
preserve the inclusions $\NCOne \subseteq \L$, $\NL\subseteq \ACOne$. We start
by giving the first definitions that preserve them. Here for \L\ and \NL\ we
define their relativizations using Wilson's stack oracle model, but limit the
height of the stack to a constant (instead of $\log(n)$). We show that the
collapse of any two classes in $\{\ACZm, \TCZ, \NCOne, \L, \NL\}$ implies the
collapse of their relativizations. Next we exhibit an oracle $\alpha$ that
makes $\ACk(\alpha)$ a proper hierarchy. This strengthens and clarifies the
separations of the relativized theories in [Takeuti, 1995]. The idea is that a
circuit whose nested depth of oracle gates is bounded by $k$ cannot compute
correctly the $(k+1)$ compositions of every oracle function. Finally we develop
theories that characterize the relativizations of subclasses of \Ptime\ by
modifying theories previously defined by the second two authors. A function is
provably total in a theory iff it is in the corresponding relativized class,
and hence the oracle separations imply separations for the relativized
theories.
