Number conserving cellular automata: new results on decidability and dynamics

Abstract

This paper is a survey on our recent results about number conserving cellular automata. First, we prove the linear time decidability of the property of number conservation. The sequel focuses on dynamical evolutions of number conserving cellular automata.

Keywords

• discrete dynamical systems
• decidability
• cellular automata
• classification
• [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]
• [math.math-co] mathematics [math]/combinatorics [math.co]
• [nlin.nlin-cg] nonlinear sciences [physics]/cellular automata and lattice gases [nlin.cg]