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 - https://www.scopus.com/pages/publications/58549106415
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
T2 - 19th International Symposium on Algorithms and Computation, ISAAC 2008
Y2 - 15 December 2008 through 17 December 2008
ER -