Communication complexity in number-conserving and monotone cellular automata

E. Goles, A. Moreira, I. Rapaport

Research output: Contribution to journalArticlepeer-review

8 Scopus citations

Abstract

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
Volume412
Issue number29
DOIs
StatePublished - 1 Jul 2011
Externally publishedYes

Keywords

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

Fingerprint

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

Cite this