Simulations between alternating CA, alternating TM and circuit families
Frank Reischle, Thomas Worsch · Repository KITopen (Karlsruhe Institute of Technology) · 1998
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.