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
