Buchholz, ThomasThomasBuchholzKlein, AndreasAndreasKleinKutrib, MartinMartinKutrib2022-09-121999-04-072022-09-121999http://nbn-resolving.de/urn:nbn:de:hebis:26-opus-1415https://jlupub.ub.uni-giessen.de/handle/jlupub/7557http://dx.doi.org/10.22029/jlupub-6991The 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.enIn Copyrightddc:004