We investigate the phenomenon of depth-reduction in commutative and no
n-commutative arithmetic circuits. We prove that in the commutative se
tting, uniform semi-unbounded arithmetic circuits of logarithmic depth
are as powerful as uniform arithmetic circuits of polynomial degree (
and unrestricted depth); earlier proofs did not work in the uniform se
tting. This also provides a unified proof of the circuit characterizat
ions of the class LOGCFL and its counting variant #LOGCFL. We show tha
t 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 sire drawn between TC1 and arithmetic circuits of polyn
omial size and degree. Then we consider non-commutative computation. W
e show that over the algebra (Sigma, max, concat), arithmetic circuit
s of polynomial size and polynomial degree can be reduced to O(log(2)
n) depth land even to O(log n) depth if unbounded-fanin gates are allo
wed). This establishes that OptLOGCFL is in AC(1). This is the first d
epth-reduction result for arithmetic circuits over a non-commutative s
emiring, and it complements the lower bounds of Kosaraju and Nisan sho
wing that depth reduction cannot be done in the general non-commutativ
e setting. We define new notions called ''short-left-paths'' and ''sho
rt-right-paths'' and we show that these notions provide a characteriza
tion of the classes of arithmetic circuits for which optimal depth red
uction is possible. This class also can be characterized using the Aux
PDA model. Finally, we characterize the languages generated by efficie
nt circuits over the semiring (2(Sigma), union, concat) in terms of s
imple one-way machines, and we investigate and extend earlier lower bo
unds on non-commutative circuits. (C) 1998-Elsevier Science B.V. All r
ights reserved.