Simulations between alternating CA, alternating TM and circuit families

Variants of cellular automata consisting of alternating instead of
deterministic finite automata are investigated, so-called uniform
alternating CA (ACA) and two types of nonuniform ACA. The former two
have been considered by Matamala (1997). It is shown that the
nonuniform ACA are time equivalent. The main contributions are fast
simulations of ACA by uniform circuit families and vice versa. It is
shown that nonuniform ACA are time equivalent to circuit families with
unbounded fan-in, and that uniform ACA are time equivalent to circuit
families with constant fan-in. Hence uniform ACA and alternating TM
are time equivalent, too, solving a problem left open by Matamala. The
results also give some evidence that a linear time simulation of
nonuniform ACA by ATM is ``unlikely'' to exist.