Number Conservation via Particle Flow in One-dimensional Cellular Automata

A number-conserving cellular automaton is a simplified model for a system ofinteracting particles. This paper contains two related constructions by whichone can find all one-dimensional number-conserving cellular automata with onekind of particle. The output of both methods is a "flow function", which describes the movementof the particles. In the first method, one puts increasingly strongerrestrictions on the particle flow until a single flow function is specified.There are no dead ends, every choice of restriction steps ends with a flow. The second method uses the fact that the flow functions can be ordered andthen form a lattice. This method consists of a recipe for the slowest flow thatenforces a given minimal particle speed in one given neighbourhood. All otherflow functions are then maxima of sets of these flows. Other questions, like that about the nature of non-deterministicnumber-conserving rules, are treated briefly at the end.Comment: 29 pages, 6 figure