TY  - UNPD
A1  - Malcher, Andreas
T1  - On two-way communication in cellular automata with a fixed number of cells
T2  - Frankfurter Informatik-Berichte ; Nr. 03,2
N2  - 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.
T3  - Frankfurter Informatik-Berichte - 03, 2 
Y1  - 2003
UR  - http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/7187
UR  - https://nbn-resolving.org/urn:nbn:de:hebis:30-71694
SN  - 1616-9107
PB  - Johann Wolfgang Goethe-Univ., Fachbereich Biologie und Informatik, Inst. für Informatik
CY  - Frankfurt am Main
ER  -