TY - GEN

T1 - Understanding a non-trivial cellular automaton by finding its simplest underlying communication protocol

AU - Goles, Eric

AU - Little, Cedric

AU - Rapaport, Ivan

N1 - Funding Information:
Partially supported by Programs Conicyt “Anillo en Redes”, Fondap, Basal-CMM, Fondecyt 1070022 and Instituto Milenio ICDB.

PY - 2008

Y1 - 2008

N2 - In the present work we find a non-trivial communication protocol describing the dynamics of an elementary CA, and we prove that there are no simpler descriptions (protocols) for such CA. This is, to our knowledge, the first time such a result is obtained in the study of CAs. More precisely, we divide the cells of Rule 218 into two groups and we describe (and therefore understand) its global dynamics by finding a protocol taking place between these two parts. We assume that x∈ ∈{0,1} n is given to Alice while y∈ ∈{0,1} n is given to Bob. Let us call z(x,y)∈ ∈{0,1} the result of the dynamical interaction between the cells. We exhibit a protocol where Alice, instead of the n bits of x, sends 2⌈log(n)⌉+1 bits to Bob allowing him to compute z(x,y). Roughly, she sends 2 particular positions of her string x. By proving that any one-round protocol computing z(x,y) must exchange at least 2⌈log(n)⌉ - 5 bits, the optimality of our construction (up to a constant) is concluded.

AB - In the present work we find a non-trivial communication protocol describing the dynamics of an elementary CA, and we prove that there are no simpler descriptions (protocols) for such CA. This is, to our knowledge, the first time such a result is obtained in the study of CAs. More precisely, we divide the cells of Rule 218 into two groups and we describe (and therefore understand) its global dynamics by finding a protocol taking place between these two parts. We assume that x∈ ∈{0,1} n is given to Alice while y∈ ∈{0,1} n is given to Bob. Let us call z(x,y)∈ ∈{0,1} the result of the dynamical interaction between the cells. We exhibit a protocol where Alice, instead of the n bits of x, sends 2⌈log(n)⌉+1 bits to Bob allowing him to compute z(x,y). Roughly, she sends 2 particular positions of her string x. By proving that any one-round protocol computing z(x,y) must exchange at least 2⌈log(n)⌉ - 5 bits, the optimality of our construction (up to a constant) is concluded.

UR - http://www.scopus.com/inward/record.url?scp=58549106415&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-92182-0_53

DO - 10.1007/978-3-540-92182-0_53

M3 - Conference contribution

AN - SCOPUS:58549106415

SN - 3540921818

SN - 9783540921813

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 592

EP - 604

BT - Algorithms and Computation - 19th International Symposium, ISAAC 2008, Proceedings

Y2 - 15 December 2008 through 17 December 2008

ER -