NCCA - Some of my work

	General theory of NCCA: universality, decidability, extension of definition, numbers associated to blocks.
	1D particle automata: equivalence in the conservative case. Possible behaviors of particles: some intrinsic to CA, some decidable.
	Other conservations: number of sites in each state, momentum.
	Monotone case: characterization of 1D monotone CA, particle representation.
	Catalog: one-dimensional NCCA and decreasing CA.
	Two-dimensional NCCA and particle automata: characterizations and listings.

• 1D NCCA are universal. Moreover, they are intrinsically universal, in the sense defined in Ollinger [3] (I don't know which is the original reference for this definition): any 1D CA can be simulated by a 1D NCCA -i.e., for each 1D CA F there exists a 1D NCCA G such that F is a subautomaton of a rescaling of G.
• Number-conservation is decidable. I consider this in the general sense of this question: if I have a CA, is it possible to associate numbers to its states, so that it becomes a NCCA?
• The previous question is sometimes answered with a set of numbers which is not of the form {0,...,q-1}, whereas all the literature considers state sets of this form. Do we need to extend NCCA to accomodate this situation? I show that nothing important is added: any 1D NCCA with set of states in the integers, is a subautomaton of a 1D NCCA with a set of states of the canonical form.

1D particle automata:
In [2] we formalize motion representations as particle automata (PA). We show -again, as Fuks and Pivato before- that 1D NCCA are equivalent to 1D conservative PA. Then we discuss some properties that PA may exhibit:

• Anticipation: a particle moves to a site where there is (still) not enough space to accomodate it.
• Order preservation: the order of the particles along Z is preserved by the particle dynamics.
• Local cycles: there is a local, cyclic replacement of particles (with the effect that "nothing happens").
• Global cycles: an infinite chain of particles replacements (it is equivalent to a chain of cyclic replacements in a periodic configuration).

For any 1D NCCA, the equivalence theorem (and also those of other authors) yields a PA that preserves order (and therefore prevents local cycles). Furthermore, we show that anticipation and global anticipatory cycles may be intrinsic to some NCCA: no PA exists for them where these behaviours are avoided. Finally, we show how to decide, for a given 1D NCCA, whether global anticipatory cycles can be avoided or not (they may be unwanted, since they imply that the "drivers" are using the non-local information "I'm on a thorus" or "I'm in an infinite queue").

Other conservations:
In [2] we consider two further kinds of conservation: state-conservation (where the number of sites in each state is conserved) and momentum conservation (where the sum of the displacements of the particles remains the same). We characterize state-conservating CA, and show how to construct an appropriate PA for them (in this case, it makes more sense to consider each state as a different kind of particle, and not as the number of particles in a cell). We also characterize momentum conservation, and show that it depends only on the NCCA, and not on the particular PA that we use to represent it (in spite of being defined -and making sense- only for the PA).

Monotone CA:
In [2] we also extend the theory, in order to include CA where the sum of the states is not constant, but monotone. We give a characterization of such CA (in 1D). Furthermore, we prove that for each non-increasing 1D CA, there is a PA (with vanishing particles) representing it. Needless to say, that to any non-increasing CA there corresponds a non-decreasing CA; we can deal with non-decreasing CA by replacing "particles" with "no-particles" and vice versa.

Catalog of 1D CA:
Here are the numbers of 1D number-conserving CA (NCCA), state-conserving CA (SCCA), non-increasing CA (DCA), and maximal DCA (those that are not dominated by another one), for small values numbers of states (q) and small sizes of the neighbourhood (n). Click on the underlined numbers to download data sets; they are text files, with one CA rule in each line. For each rule, the image of all the qⁿ configurations is written by starting with f(0,...,0), ending with f(q-1,...,q-1).

q	n	NCCA	SCCA1	DCA	max DCA2
2	2	2	2	6	2
2	3	5	5	46	5
2	4	22	22	2756	38
2	5	428	428	?	?
2	6	133184	133184	?	?
3	2	4	2	708	6
3	3	144	15	?	?
3	4	5448642	?	?	?
4	2	10	2	37322576	?
4	3	89588	89	?	?
1: for q=2, all NCCA are SCCA 2: the files contain only DCA that are not NCCA

2D NCCA and PA:
I characterized 2D NCCA (in the same that was published by Durand et al), for rectangular neighbourhoods, and also determined specific characterizations for the small neighbourhoods (all polyominoes of sizes up to 5). Using them (and the characterization for the rectangle 2x3), I listed exhaustively the NCCA with few states. The resulting rules can be seen in an applet in the software section; many rules have been removed in order to avoid most of the repetitions between the different sets. The data sets used in the applet can be downloaded in a zipped file; the format of each file is similar to the files of 1D rules described above, with the addition of a header; to number the configurations, the positions in the polyomino are numbered from the top to the bottom, from the left to the right. An old report on this is here.

On the other hand, I also listed two-dimensional particle automata with small neighbourhoods. All the PA with von Neumann neighbourhood and 2 states can be seen in an applet in the software section; there is also a sample of the PA with Moore's neighbourhood.

References

1. A. Moreira, 2003. Universality and Decidability of Number-Conserving Cellular Automata. Theoretical Computer Science 292, pp. 711-721. .
2. A. Moreira, N. Boccara, E. Goles, 2004. On Conservative and Monotone One-dimensional Cellular Automata and Their Particle Representation. Theoretical Computer Science 325, pp. 285-316. .
3. N. Ollinger, 2001. Bilinear Intrinsically Universal Cellular Automata. Research Report N. 2001-11, LIP, École Normale Supériore de Lyon. Shorter version in LNCS 2138, p. 396 ff.