On two-way communication in cellular automata with a fixed number of cells
- The effect of adding two-way communication to k cells one-way cellular automata (kC-OCAs) on their size of description is studied. kC-OCAs are a parallel model for the regular languages that consists of an array of k identical deterministic finite automata (DFAs), called cells, operating in parallel. Each cell gets information from its right neighbor only. In this paper, two models with different amounts of two-way communication are investigated. Both models always achieve quadratic savings when compared to DFAs. When compared to a one-way cellular model, the result is that minimum two-way communication can achieve at most quadratic savings whereas maximum two-way communication may provide savings bounded by a polynomial of degree k.
| Verfasserangaben: | Andreas Malcher |
|---|---|
| URN: | urn:nbn:de:hebis:30-71694 |
| ISSN: | 1616-9107 |
| Titel des übergeordneten Werkes (Deutsch): | Frankfurter Informatik-Berichte ; Nr. 03,2 |
| Schriftenreihe (Bandnummer): | Frankfurter Informatik-Berichte (03, 2) |
| Verlag: | Johann Wolfgang Goethe-Univ., Fachbereich Biologie und Informatik, Inst. für Informatik |
| Verlagsort: | Frankfurt am Main |
| Dokumentart: | Arbeitspapier |
| Sprache: | Englisch |
| Jahr der Fertigstellung: | 2003 |
| Jahr der Erstveröffentlichung: | 2003 |
| Veröffentlichende Institution: | Universitätsbibliothek Johann Christian Senckenberg |
| Datum der Freischaltung: | 16.10.2009 |
| Seitenzahl: | IV, 12 S. |
| HeBIS-PPN: | 21973075X |
| Institute: | Informatik und Mathematik / Informatik |
| DDC-Klassifikation: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik |
| Lizenz (Deutsch): |  Deutsches Urheberrecht |
