TY - JOUR

T1 - On conservative and monotone one-dimensional cellular automata and their particle representation

AU - Moreira, Andrés

AU - Boccara, Nino

AU - Goles, Eric

N1 - Funding Information:
We want to thank M. Morvan and the Laboratoire d’ Informatique Algorithmique (LIAFA) of the University of Paris VII; this work was started during a visit of A. Mor-eira to that unit. We were also supported by the FONDAP program in Applied Mathematics, and A. Moreira was partially supported by the CONICYT Ph.D. fellowship.

PY - 2004/10/1

Y1 - 2004/10/1

N2 - Number-conserving (or conservative) cellular automata (CA) have been used in several contexts, in particular traffic models, where it is natural to think about them as systems of interacting particles. In this article we consider several issues concerning one-dimensional cellular automata which are conservative, monotone (specially "non-increasing"), or that allow a weaker kind of conservative dynamics. We introduce a formalism of "particle automata", and discuss several properties that they may exhibit, some of which, like anticipation and momentum preservation, happen to be intrinsic to the conservative CA they represent. For monotone CA we give a characterization, and then show that they too are equivalent to the corresponding class of particle automata. Finally, we show how to determine, for a given CA and a given integer b, whether its states admit a b-neighborhood-dependent relabeling whose sum is conserved by the CA iteration; this can be used to uncover conservative principles and particle-like behavior underlying the dynamics of some CA. Complements at http://www.dim.uchile.cl/~anmoreir/ncca

AB - Number-conserving (or conservative) cellular automata (CA) have been used in several contexts, in particular traffic models, where it is natural to think about them as systems of interacting particles. In this article we consider several issues concerning one-dimensional cellular automata which are conservative, monotone (specially "non-increasing"), or that allow a weaker kind of conservative dynamics. We introduce a formalism of "particle automata", and discuss several properties that they may exhibit, some of which, like anticipation and momentum preservation, happen to be intrinsic to the conservative CA they represent. For monotone CA we give a characterization, and then show that they too are equivalent to the corresponding class of particle automata. Finally, we show how to determine, for a given CA and a given integer b, whether its states admit a b-neighborhood-dependent relabeling whose sum is conserved by the CA iteration; this can be used to uncover conservative principles and particle-like behavior underlying the dynamics of some CA. Complements at http://www.dim.uchile.cl/~anmoreir/ncca

KW - Cellular automata

KW - Interacting particles

KW - Number-conserving systems

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

U2 - 10.1016/j.tcs.2004.06.010

DO - 10.1016/j.tcs.2004.06.010

M3 - Article

AN - SCOPUS:4444268808

SN - 0304-3975

VL - 325

SP - 285

EP - 316

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 2 SPEC. ISS.

ER -