NCCA (and related) - Work I have heard about

Please email me on any omissions -or unfair treatments- in this page.

Some contexts in which NCCA appear are the models of highway traffic [1, 15, 20, 26, 35, 40, 41, 42, 45, 44, 46, 47], fluid flows [16], and eutectic alloys [27, 28]. In the case of highway traffic the literature is already huge, and only a rather arbitrary selection of references is given here. There are also many interesting studies directly related to these traffic models [2, 3, 4, 19, 30, 50]; again, this references are far from exhaustive.

Researchers in several places have been attracted to the study of NCCA; in alphabetic order, I can mention Nino Boccara in France (whose colaborations with Henry Fuks [5, 6] contributed to the interest in the area, and who introduced me to the subject), the group of Bruno Durand in France [13, 14], Fuks in Canada [17, 18], Petr Kurka in the Chech Republic [32], Kenichi Morita and Katsunobu Imai in Japan [25, 37, 39], Marco Pivato in USA [45], and myself. (Please email if I'm omitting some name.)

Boccara and Fuks gave necessary and sufficient conditions for a one-dimensional CA to be a NCCA, first for two states [5] and then for an arbitrary number of states [6] (this second one can be derived from a general theorem on conservative quantities in cellular automata, due to Hattori and Takesue [22, 49]). They used these characterizations for the exhaustive determination of all 1D NCCA with few states and small neighbourhoods, and gave motion representations (that is, equivalent representations in terms of the interaction of particles) for all the NCCA they studied. In [17] Fuks showed that motion representations could always be constructed for 1D NCCA with two states (and where therefore an alternative paradigm for the same systems). A more recent work by Fuks extends the ideas of number-conservation to stochastic cellular automata [18].

Pivato [45] gives a general treatment of conserved quantities in 1D CA, showing how to construct all the CA who satisfy a given conservation law. He also (and independently) shows the equivalence of 1D NCCA and their particles representations, now for an arbitrary number of states. In fact, I know of at least 4 different proofs of this same result, two of them by myself.

Durand et al undertook the painful writing of the generalization of the characterization of NCCA to 2 and then d dimensions [14] (a few years ago Boccara and I refused to go through the horrible notation which was required to do it). In this way, they show that number-conservation is a decidable property (at least in some sense; in [36] I show that this is also true in another one). They also show the equivalence of three different (periodic, finite and measure-theoretical) notions of number-conservation. In [13] they study the possible dynamical properties of 1D NCCA; they intersect the CA classifications of Kurka [31] and Braga et al [9, 10], and for each of the resulting classes they either exhibit a number-conserving example or prove that none can exist.

A recent preprint by Kurka [32] deals with CA with vanishing particles; this extends the idea of conserved quantities to that of monotone quantities. He works with a very general definition of "particle", by associating weights to (possibly unbounded) local patterns, gives some sufficient conditions under which the probability of particles converges to zero, and applies them to some interesting particular cases. His characterization of CA with vanishing particles extends mine, as we could noticed after we exchanged preprints some months ago.

Two articles by Morita, Imai and other collaborators [38, 39] use partitioned number-conserving (and reversible) CA. This is not exactly the same as a NCCA, since the reduction from a partitioned CA to a non-partitioned one does not preserve number-conservation. In these articles they show the computational universality of this class of automata, by simulating a counter machine which is known to be universal. A recent and nice work by the same group [25] deals with "normal" 2D NCCA; they give the characterization for von Neumann's neighbourhood, and give two particular 2D NCCA, one in which they embed a logically universal model (the "Wireworld") -thus showing universality- and one in which they embed a self-reproducing structure (Langton's loops). (I show the universality of "normal" 1D NCCA in [36].)

For the sake of completeness and to avoid confusions, it is worth mentioning other contexts in which particles have been considered. On one hand, there are the interacting particle systems (IPS), with a long history in probability theory [33], and the lattice gases, some of them with associated CA models [8]; in general, they cannot be written as conservative CA. The well-known two-dimensional Margolus CA [34] is number-conserving and was designed to allow rich interactions of particles; it does not fit in the definition given here, because of its alternating neighborhood. Particles have been widely used in computer graphics [23], sometimes using CA with a Margolus neighborhood [48]. The word "particle" is also used to describe emergent particle-like structures that propagate in CA [7, 12, 21, 24]; in this last sense, its use is close to the spirit of the work of Kurka [32] and myself [37].

References

  1. V. Belitsky, J. Krug, E.J. Neves, G.M. Schutz, 2001. A cellular automaton model for two-lane traffic. J. Stat. Phys. 103, pp. 945-971. .
  2. M. Blank, 2003. Ergodic properties of a simple deterministic traffic flow model. J. Stat. Phys. 111, pp. 903-930.
  3. M. Blue and B. Bush. Information content in the Nagel-Schreckenberg cellular automata traffic model. To appear in Physical Review E. .
  4. N. Boccara, 2001. On the existence of a variational principle for deterministic cellular automaton models of highway traffic flow. International Journal of Modern Physics C 12, pp. 143-158. .
  5. N. Boccara and H. Fuks, 1998. Cellular automaton rules conserving the number of active sites. Journal of Physics A: math. gen. 31, pp. 6007-6018. .
  6. N. Boccara and H. Fuks, 2001. Number-conserving cellular automaton rules. Fundamenta Informaticae 52, pp. 1-13. .
  7. N. Boccara, J. Nasser, M. Roger, 1991. Particle-like structures and their interactions in spatio-temporal patterns generated by one-dimensional deterministic cellular automaton rules. Physical Review A 44, pp. 866-875.
  8. J.P. Boon, 1991. Statistical Mechanics and Hydrodynamics of Lattice Gas Automata: An Overview. Physica D 47, pp. 3-8.
  9. G. Braga et al, 1993. Complex chaotic behaviour of a class of subshift cellular automata. Complex Systems 7, pp.269-296.
  10. G. Braga et al, 1995. Pattern growth in elementary cellular automata. Theoretical Computer Science 145, pp. 1-26.
  11. D. Chowdhury, V. Guttal, K. Nishinari, A. Schadschneider, 2002. A cellular-automata model of flow in ant trails: non-monotonic variation of speed with density. J. Phys. A: Math. Gen. 35, pp. L573-L577. .
  12. R. Das, M. Mitchell, J.P. Crutchfield, 1994. A Genetic Algorithm Discovers Particle-Based Computation in Cellular Automata. In Parallel Problem Solving from Nature---PPSN III, Springer-Verlag, Berlin, pp. 344-353,
  13. B. Durand, E. Formenti, Z. Róka. Number-conserving cellular automata: from decidability to dynamics. Preprint. .
  14. B. Durand, E. Formenti, Z. Róka. Number-conserving cellular automata I: decidability. Theoretical Computer Science 299, pp. 523-535.
  15. J. Esser and M. Schreckenberg, 1997. Microscopic simulations of urban traffic based on cellular automata. International Journal of Modern Physics C 8, pp. 1025-1036. .
  16. U. Frisch et al, 1986. Lattice-Gas Automata for the Navier-Stokes equation. Physical Review Letters 56, pp. 1505-1508.
  17. H. Fuks, 2000. A class of cellular automata equivalent to deterministic particle systems. In Hydrodynamic Limits and Related Topics, published by the American Mathematical Society. .
  18. H. Fuks. Probabilistic cellular automata with conserved quantities. Preprint. .
  19. H. Fuks, 1999. Exact results for deterministic cellular automata traffic models. Phys. Rev. E 60, pp. 197-202. .
  20. M. Fukui and Y. Ishibashi, 1996. Traffic flow in 1D cellular automaton model including cars moving with high speed. J. Phys. Soc. Japan 65 pp. 1868-1870.
  21. J.E. Hanson, J.P. Crutchfield, 1997. Computational mechanics of cellular automata: An example. Physica D 103, pp. 169-189. .
  22. T. Hattori, S. Takesue, 1991. Additive conserved quantities in discrete-time lattice dynamical systems. Physica D 49, 295-322.
  23. R.W. Hocknew, J.W. Eastwood, 1988. Computer Simulation Using Particles, published by Adam Hilger, New York.
  24. W. Hordijk, C. Shalizi, J.P. Crutchfield, 2001. Upper bound on the products of particle interactions in cellular automata. Physica D 154, pp. 240-258. .
  25. K. Imai, K. Fujita, C. Iwamoto, K. Morita, 2002. Embedding a Logically Universal Model and a Self-Reproducing Model into Number-Conserving Cellular Automata. Lecture Notes in Computer Science 2509. .
  26. B. Kerner, S. Klenov, D. Wolf, 2002. Cellular automata approach to three-phase traffic theory. J. Phys. A: Math. Gen. 35, pp. 9971-10013. .
  27. T. Kohyama, 1989. Cellular automata with particle conservation. Progress of Theoretical Physics 81, pp. 47-59. .
  28. T. Kohyama, 1991. Cluster growth in particle-conserving cellular automata. Journal of Statistical Physics 63, pp. 637-651.
  29. L. Kotze, W. H. Steeb, 1988. Conservation Laws in Cellular Automata. In Finite Dimensional Integrable Nonlinear Dynamical Systems, published by World Scientific, New Jersey, pp. 333-346.
  30. J.V. Kujala, T.J. Lukka, 2002. Exact limiting solutions for certain deterministic traffic rules. .
  31. P. Kurka, 1997. Languages, Equicontinuity and Attractors in Cellular Automata. Ergodic Theory & Dynamical Systems 17, pp. 417-433.
  32. P. Kurka. Cellular Automata With Vanishing Particles. Preprint.
  33. T.M. Ligget, 1985. Interacting Particle Systems, published by Springer Verlag, Berlin.
  34. N. Margolus, 1984. Physics-like Models of Computation. Physica D 10, pp. 81-95.
  35. J. Matsukidaira, K. Nishinari, 2003. Euler-Lagrange correspondence of cellular automaton for traffic-flow models. Phys. Rev. Lett. 90.
  36. A. Moreira, 2003. Universality and Decidability of Number-Conserving Cellular Automata. Theoretical Computer Science 292, pp. 711-721. .
  37. 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. .
  38. K. Morita and K. Imai, 1998. Number-Conserving Reversible Cellular Automata and Their Computation-Universality. In the Proceedings of Satellite Workshop on Cellular Automata MFCS'98, Brno., pp. 51-68. .
  39. K. Morita, Y. Tojima, K. Imai, 1999. A Simple Computer Embedded in a Reversible and Number-Conserving Two-Dimensional Cellular Space. In the Proceedings of LA Symposium'99, Hakone. .
  40. K. Nagel, 1996. Particle hopping models and traffic flow theory. Physical Review E 53, pp. 4655-4672. .
  41. K. Nagel and H. Herrmann, 1993. Deterministic models for traffic jams. Physica A 199, pp. 254-269. .
  42. K. Nagel and M. Schreckenberg, 1992. A cellular automaton model for freeway traffic. J. Physique I 2, pp. 2221-2229.
  43. K. Nagel, D. Wolf, P. Wagner, P. Simon, 1998. Two-lane traffic rules for cellular automata: A systematic approach. Physical Review E 58, pp. 1425-1437. .
  44. K. Nishinari and D. Takahashi. A family of multi-value cellular automaton model for traffic flow. .
  45. M. Pivato, 2002. Conservation laws in cellular automata. Nonlinearity 15, pp. 1781-1794. .
  46. P. Simon and H. Gutowitz. Exact limiting solutions for certain deterministic traffic rules. .
  47. P. Simon and K. Nagel, 1998. Simplified cellular automaton model for city traffic. Physical Review E 58, pp. 1286-1295. .
  48. Y. Takai, K. Ecchu, N. Takai, 1995. A cellular automaton model of particle motions and its applications. The Visual Computer 11, pp. 240-252.
  49. S. Takesue, 1995. Staggered invariants in cellular automata. Complex Systems 9, pp. 149-168.
  50. B. Wang et al, 1998. Statistical mechanical approach to Fukui-Ishibashi traffic flow models. Physical Review E 57, p. 2568.
Last updated: June 22, 2003. © Andrés Moreira