TY - JOUR
T1 - Traced communication complexity of cellular automata
AU - Goles, Eric
AU - Guillon, Pierre
AU - Rapaport, Ivan
N1 - Funding Information:
✩ This work has been supported by the ECOS-Sud Project, Academy of Finland project 131558 (P. G.), Fondecyt 1070022, 1090156, BASAL-CMM (I. R.), Fondecyt∗ Correspondingauthorat:DIM-CMM,UMICNRS2807,UniversidaddeChile,Santiago,Chile.1100003,BASAL-CMM,AnilloAct88,SFI-SantaFe(E.G.). E-mail addresses: eric.chacc@uai.cl (E. Goles), pguillon@dim.uchile.cl (P. Guillon), rapaport@dim.uchile.cl (I. Rapaport).
PY - 2011/7/8
Y1 - 2011/7/8
N2 - 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.
AB - 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.
KW - Cellular automata
KW - Communication complexity
UR - http://www.scopus.com/inward/record.url?scp=79957872452&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2011.02.025
DO - 10.1016/j.tcs.2011.02.025
M3 - Article
AN - SCOPUS:79957872452
SN - 0304-3975
VL - 412
SP - 3906
EP - 3916
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 30
ER -