Real-time language recognition by alternating cellular automata - Buchholz, Thomas; Klein, Andreas; Kutrib, Martin; Justus Liebig University Giessen (My University, 1999)
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 socalled nonuniform ACAs. Our considerations center on space bounded realtime computations. In particular, we prove that there is no difference in acceptance power regardless whether oneway or twoway communication lines are provided. Moreover, the relations between realtime ACAs and deterministic (CA) and nondeterministic (NCA) cellular automata are investigated. It is proved that even the realtime ACAs gain exponential speedup against nondeterministic NCAs. Comparing ACAs with deterministic CAs it is shown that realtime ACAs are strictly more powerful than realtime CAs.
Keywords: ddc:004