Communication complexity in number-conserving and monotone cellular automata

E. Goles, A. Moreira, I. Rapaport

Research output: Contribution to journalArticlepeer-review

10 Scopus citations


One third of the elementary cellular automata (CAs) are either number-conserving (NCCAs) or monotone (increasing or decreasing). In this paper we prove that, for all of them, we can find linear or constant communication protocols for the prediction problem. In other words, we are able to give a succinct description for their dynamics. This is not necessarily true for general NCCAs. In fact, we also show how to explicitly construct, from any CA, a new NCCA which preserves the original communication complexity.

Original languageEnglish
Pages (from-to)3616-3628
Number of pages13
JournalTheoretical Computer Science
Issue number29
StatePublished - 1 Jul 2011
Externally publishedYes


  • Cellular automata
  • Communication complexity
  • Elementary cellular automata
  • Number-conserving


Dive into the research topics of 'Communication complexity in number-conserving and monotone cellular automata'. Together they form a unique fingerprint.

Cite this