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 ide
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.
show moreshow less

Download full text files

Export metadata

  • Export Bibtex
  • Export RIS

Additional Services

    Share in Twitter Search Google Scholar
Metadaten
Author:Andreas Malcher
URN:urn:nbn:de:hebis:30-71694
ISSN:1616-9107
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
Language:English
Year of Completion:2003
Year of first Publication:2003
Publishing Institution:Univ.-Bibliothek Frankfurt am Main
Release Date:2009/10/16
Pagenumber:IV, 12 S.
HeBIS PPN:21973075X
Institutes:Informatik
Dewey Decimal Classification:004 Datenverarbeitung; Informatik
Sammlungen:Universitätspublikationen
Licence (German):License Logo Veröffentlichungsvertrag für Publikationen

$Rev: 11761 $