Real-time language recognition by alternating cellular automata
Loading...
Date
Advisors/Reviewers
Further Contributors
Contributing Institutions
Publisher
Journal Title
Journal ISSN
Volume Title
Publisher
License
Quotable link
DOI:
http://dx.doi.org/10.22029/jlupub-6991Abstract
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.Link to publications or other datasets
Description
Notes
Original publication in
Original publication in
Anthology
Collections
URI of original publication
Forschungsdaten
Series
IFIG Research Report; 9904 / 1999