Communications in cellular automata

Eric Goles
Pierre-Etienne Meunier
Ivan Rapaport
Guillaume Theyssier

The goal of this paper is to show why the framework of communication complexity seems suitable for the study of cellular automata. Researchers have tackled different algorithmic problems ranging from the complexity of predicting to the decidability of different dynamical properties of cellular automata. But the difference here is that we look for communication protocols arising in the dynamics itself. Our work is guided by the following idea: if we are able to give a protocol describing a cellular automaton, then we can understand its behavior.

In Turlough Neary, Damien Woods, Tony Seda and Niall Murphy: Proceedings International Workshop on The Complexity of Simple Programs (CSP 2008), Cork, Ireland, 6-7th December 2008, Electronic Proceedings in Theoretical Computer Science 1, pp. 81–92.
Published: 25th June 2009.

ArXived at: bibtex PDF

Comments and questions to:
For website issues: