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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Author:Andreas Malcher
Parent Title (German):Frankfurter Informatik-Berichte ; Nr. 03,2
Series (Serial Number):Frankfurter Informatik-Berichte (03, 2)
Publisher:Johann Wolfgang Goethe-Univ., Fachbereich Biologie und Informatik, Inst. für Informatik
Place of publication:Frankfurt am Main
Document Type:Working Paper
Year of Completion:2003
Year of first Publication:2003
Publishing Institution:Universitätsbibliothek Johann Christian Senckenberg
Release Date:2009/10/16
Page Number:IV, 12 S.
Institutes:Informatik und Mathematik / Informatik
Dewey Decimal Classification:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik
Licence (German):License LogoDeutsches Urheberrecht