Real-time language recognition by alternating cellular automata

Abstract

The capabilities of alternating cellular automata (ACA) to accept formal languages are investigated. Several notions of alternation in cellular automata have been proposed. Here we study so­called nonuniform ACAs. Our considerations center on space bounded real­time computations. In particular, we prove that there is no difference in acceptance power regardless whether one­way or two­way communication lines are provided. Moreover, the relations between real­time ACAs and deterministic (CA) and nondeterministic (NCA) cellular automata are investigated. It is proved that even the real­time ACAs gain exponential speed­up against nondeterministic NCAs. Comparing ACAs with deterministic CAs it is shown that real­time ACAs are strictly more powerful than real­time CAs.