Giessener Elektronische Bibliothek

GEB - Giessener Elektronische Bibliothek

Hinweis zum Urheberrecht

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URL: http://geb.uni-giessen.de/geb/volltexte/1999/141/


Real-time language recognition by alternating cellular automata

Buchholz, Thomas ; Klein, Andreas ; Kutrib, Martin


pdf-Format: Dokument 1.pdf (231 KB)
ps gepackt: class="frontdoor">Dokument1.gz (126 KB)

Bookmark bei Connotea Bookmark bei del.icio.us
Universität Justus-Liebig-Universität Gießen
Institut: Institut für Informatik
Fachgebiet: Informatik
DDC-Sachgruppe: Informatik
Dokumentart: ResearchPaper (Forschungsbericht, Arbeitspapier)
Zeitschrift, Serie: IFIG Research Report ; 9904 / 1999
Sprache: Englisch
Erstellungsjahr: 1999
Publikationsdatum: 08.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.