Number-conserving cellular automata and communication complexity: A numerical exploration beyond elementary CAs

Eric Goles, Andrés Moreira

Resultado de la investigación: Contribución a una revistaArtículorevisión exhaustiva

Resumen

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.

Idioma originalInglés
Páginas (desde-hasta)151-165
Número de páginas15
PublicaciónJournal of Cellular Automata
Volumen7
N.º2
EstadoPublicada - 2012
Publicado de forma externa

Huella

Profundice en los temas de investigación de 'Number-conserving cellular automata and communication complexity: A numerical exploration beyond elementary CAs'. En conjunto forman una huella única.

Citar esto