Traced communication complexity of cellular automata

Eric Goles, Pierre Guillon, Ivan Rapaport

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


We study cellular automata with respect to a new communication complexity problem: each of two players know half of some finite word, and must be able to tell whether the state of the central cell will follow a given evolution, by communicating as little as possible between each other. We present some links with classical dynamical concepts, especially equicontinuity, expansivity, entropy and give the asymptotic communication complexity of most elementary cellular automata.

Original languageEnglish
Pages (from-to)3906-3916
Number of pages11
JournalTheoretical Computer Science
Issue number30
StatePublished - 8 Jul 2011
Externally publishedYes


  • Cellular automata
  • Communication complexity


Dive into the research topics of 'Traced communication complexity of cellular automata'. Together they form a unique fingerprint.

Cite this