TY - JOUR
T1 - Communication complexity in number-conserving and monotone cellular automata
AU - Goles, E.
AU - Moreira, A.
AU - Rapaport, I.
N1 - Funding Information:
This work was partially supported by Fondecyt projects 1080592 (AM and EG) and 1090156 (IR), BASAL-CMM project (EG), Conicyt Anillo ACT-88, as well as DGIP-UTFSM grant 241016 (AM). Part of this work was done during a 2010 stay of EG at the Santa Fe Institute.
PY - 2011/7/1
Y1 - 2011/7/1
N2 - 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.
AB - 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.
KW - Cellular automata
KW - Communication complexity
KW - Elementary cellular automata
KW - Number-conserving
UR - http://www.scopus.com/inward/record.url?scp=79956373922&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2011.03.008
DO - 10.1016/j.tcs.2011.03.008
M3 - Article
AN - SCOPUS:79956373922
SN - 0304-3975
VL - 412
SP - 3616
EP - 3628
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 29
ER -