TY - JOUR

T1 - Number-conserving cellular automata and communication complexity

T2 - A numerical exploration beyond elementary CAs

AU - Goles, Eric

AU - Moreira, Andrés

PY - 2012

Y1 - 2012

N2 - We perform a numerical exploration of number-conserving cellular automata (NCCA) beyond the class of elementary CAs, in search of examples with high communication complexity. We consider some possible generalizations of the elementary rule 184 (a minimal model of traffic, which is the only non-trivial elementary NCCA), as well as the classes of NCCAs which minimally extend either the radius or the state set (with respect to the 2 states and radius 1 of the elementary case). Both for 3 states and radius 1, and for 2 states and radius 2, NCCA appear that are conjectured to have maximal (exponential) communication complexity. Examples are given also for (conjectured) linear and quadratic behaviour.

AB - We perform a numerical exploration of number-conserving cellular automata (NCCA) beyond the class of elementary CAs, in search of examples with high communication complexity. We consider some possible generalizations of the elementary rule 184 (a minimal model of traffic, which is the only non-trivial elementary NCCA), as well as the classes of NCCAs which minimally extend either the radius or the state set (with respect to the 2 states and radius 1 of the elementary case). Both for 3 states and radius 1, and for 2 states and radius 2, NCCA appear that are conjectured to have maximal (exponential) communication complexity. Examples are given also for (conjectured) linear and quadratic behaviour.

KW - Communication Complexity

KW - Number-Conserving

KW - One-dimensional Cellular Automata

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

M3 - Article

AN - SCOPUS:84859461499

VL - 7

SP - 151

EP - 165

JO - Journal of Cellular Automata

JF - Journal of Cellular Automata

SN - 1557-5969

IS - 2

ER -