Giessener Elektronische Bibliothek

GEB - Giessener Elektronische Bibliothek

Real-time language recognition by alternating cellular automata

Buchholz, Thomas ; Klein, Andreas ; Kutrib, Martin


Zum Volltext im pdf-Format: Dokument 1.pdf (231 KB)


Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:hebis:26-opus-1415
URL: http://geb.uni-giessen.de/geb/volltexte/1999/141/


Universität Justus-Liebig-Universit√§t Gie√üen
Institut: Institut f√ľr Informatik
Fachgebiet: Informatik
DDC-Sachgruppe: Informatik
Dokumentart: ResearchPaper
Zeitschrift, Serie: IFIG Research Report ; 9904 / 1999
Sprache: Englisch
Erstellungsjahr: 1999
Publikationsdatum: 07.04.1999
Kurzfassung auf Englisch: 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.
Lizenz: Veröffentlichungsvertrag für Publikationen ohne Print on Demand