We investigate the phenomenon of depth-reduction in commutative
and non-commutative arithmetic circuits. We prove that in the
commutative setting, uniform semi-unbounded arithmetic circuits of
logarithmic depth are as powerful as uniform arithmetic circuits of
polynomial degree; earlier proofs did not work in the uniform
setting. This also provides a unified proof of the circuit
characterizations of LOGCFL and \#LOGCFL.

We show that AC$^1$ has no more power than arithmetic circuits of
polynomial size and degree $n^{O(\log \log n)}$ (improving the
trivial bound of $n^{O(\log n)}$). Connections are drawn between
TC$^1$ and arithmetic circuits of polynomial size and degree.

Then we consider non-commutative computation, and show that some
depth reduction is possible over the algebra ($\Sigma^*,$ max,
concat), thus establishing that OptLOGCFL is in AC$^1$. This is
the first depth-reduction result for arithmetic circuits over
a noncommutative semiring, and it complements the lower bounds of
\cite{nisan,kosaraju} showing that depth reduction cannot be done
in the general noncommutative setting.

We define new notions called ``short-left-paths'' and ``short-right-
paths'' and we show that these notions provide a characterization of
the classes of arithmetic circuits for which optimal depth-reduction
is possible. This class also can be characterized using the AuxPDA
model.

Finally, we characterize the languages generated by efficient
circuits over the (union, concat) semiring in terms of simple
one-way machines, and we investigate and extend earlier lower
bounds on non-commutative circuits.