Number-Conserving Cellular Automata and Communication Complexity: A Numerical Exploration Beyond Elementary CAs
Goles
E
author
Moreira
A
author
2012
English
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 stales and radius 2, NCCA appear that are conjectured to have maximal (exponential) communication complexity. Examples are given also for (conjectured) linear and quadratic behaviour.
Number-Conserving
Communication Complexity
One-dimensional Cellular Automata
WOS:000302978700004
exported from refbase (show.php?record=210), last updated on Mon, 14 May 2012 09:56:05 -0400
text
http://www.oldcitypublishing.com/JCA/JCAabstracts/JCA7.2abstracts/JCAv7n2p151-165Goles.html
files/144_Goles+Moreira2012.pdf
http://www.oldcitypublishing.com/JCA/JCAabstracts/JCA7.2abstracts/JCAv7n2p151-165Goles.html
Goles+Moreira2012
Journal Of Cellular Automata
J. Cell. Autom.
2012
Old City Publishing Inc
continuing
periodical
academic journal
7
2
151
165
1557-5969