Cellular automata and communication complexity

The model of cellular automata is fascinating because very simple local rules can generate complex global behaviors. The relationship between local and global function is subject of many studies. We tackle this question by using results on communication complexity theory and, as a by-product, we pro...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2004-08, Vol.322 (2), p.355-368
Main Authors: Dürr, Christoph, Rapaport, Ivan, Theyssier, Guillaume
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Automata. Abstract machines. Turing machines
Cellular automata
Communication complexity
Computer science
control theory
systems
Exact sciences and technology
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The model of cellular automata is fascinating because very simple local rules can generate complex global behaviors. The relationship between local and global function is subject of many studies. We tackle this question by using results on communication complexity theory and, as a by-product, we provide (yet another) classification of cellular automata.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2004.03.017