Number Conservation via Particle Flow in One-dimensional Cellular Automata

• Autorzy: Redeker, Markus
• Języki publikacji: EN

Abstrakty

EN

A number-conserving cellular automaton is a simplified model for a system of interacting particles. This paper contains two related constructions by which one can find all one-dimensional number-conserving cellular automata with one kind of particle. The output of both methods is a "flow function", which describes the movement of the particles. In the first method, one puts increasingly stronger restrictions 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 and then form a lattice. This method consists of a recipe for the slowest flow that enforces a given minimal particle speed in one given neighbourhood. All other flow functions are then maxima of sets of these flows. Other questions, like that about the nature of non-deterministic number-conserving rules, are treated briefly at the end.

Słowa kluczowe

EN

Nonlinear Sciences - Cellular Automata and Lattice Gases; 37B15

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2022
• Tom: Vol. 187 nr 1
• Strony: 31--59
• Opis fizyczny: Bibliogr. 10 poz.

Twórcy

autor

Redeker, Markus

• Hamburg, Germany ,

Bibliografia

• [1] Hattori T, Takesue S. Additive conserved quantities in discrete-time lattice dynamical systems. Physica D, 1991. 49(3):295-322. doi:10.1016/0167-2789(91)90150-8.
• [2] Pivato M. Conservation Laws in Cellular Automata. Nonlinearity, 2002. 6:1781. doi:10.1088/0951-7715/15/6/305.
• [3] Imai K, Alhazov A. On Universality of Radius 1/2 Number-Conserving Cellular Automata. In: Calude CS, Hagiya M, Morita K, Rozenberg G, Timmis J (eds.), Unconventional Computation. Springer Verlag, Berlin, Heidelberg. 2010 pp. 45-55. ISBN-978-3-642-13523-1.
• [4] Bhattacharjee K, Naskar N, Roy S, Das S. A Survey of Cellular Automata: Types, Dynamics, Non-uniformity and Applications. Natural Computing, 2016. pp. 1-29. doi:10.1007/s11047-018-9696-8.
• [5] Wolnik B, Nenca A, Baetens JM, De Baets B. A split-and-perturb decomposition of number-conserving cellular automata. Physica D, 2020. 413:132645. doi:10.1016/j.physd.2020.132645.
• [6] Boccara N, Fuk´s H. Cellular automaton rules conserving the number of active sites. Journal of Physics A, 1998. 31:6007-6018. doi:10.1088/0305-4470/31/28/014.
• [7] Fuk´s H. A class of cellular automata equivalent to deterministic particle systems. In: Feng S, Lawniczak AT, Varadhan SRS (eds.), Hydrodynamic Limits and Related Topics. AMS, Providence, RI, 2000 pp. 57-69.
• [8] Durand B, Formenti E, Róka Z. Number-conserving cellular automata I: decidability. Theoretical Computer Science, 2003. 299(1-3):523-535. doi:10.1016/S0304-3975(02)00534-0.
• [9] Wolfram S. Statistical Mechanics of Cellular Automata. Reviews of Modern Physics, 1983. 55:601-644. doi:10.1103/RevModPhys.55.601.
• [10] Davey BA, Priestley HA. Introduction to Lattices and Order. Cambridge University Press, Second edition, 2002. ISBN-13:978-0521784511, 10:0521784514.

Identyfikatory

DOI

10.3233/FI-222129