Cellular automata with vanishing particles

• Autorzy: Kůrka P.
• Języki publikacji: EN

Abstrakty

EN

We consider particle weight functions which assign weights to certain words. Given a cellular automaton, we search for particle weight functions, for which the total weights of configurations do not increase with time. In this case the weight of a shift-invariant Borel probability measure does not increase either, so we get a Ljapunov function on the space of measures. We give some conditions which ensure that the weight of a measure converges to zero. In particular we prove that this happens in the elementary cellular automaton rule number 18 and in a variant of the Gacs-Kurdyumov-Levin cellular automaton.

Słowa kluczowe

EN

cellular automata; particles; Borel probability measures; invariant subshifts

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2003
• Tom: Vol. 58, nr 3,4
• Strony: 203--221
• Opis fizyczny: Bibliogr. 19 poz., tab., wykr.

Twórcy

autor

Kůrka P.

• Faculty of Mathematics and Physics, Charles University in Praque, Malostramské náměstí 25. CZ-11800 Praha 1, Czechia

Bibliografia

• [1] Boccara, N., Naser, J., Roger, M.: Particle like structures and their interactions in spatiotemporal patterns generated by one-dimensional deterministic cellular-automaton rules. Physical Review A 44(2). 1991, 866-875.
• [2] Boccara, N., Fuks, H.: Cellular automaton rules conserving the number of active sites, J.Phys. A: Math. Gen. 31, 1998, 6007.
• [3] Boccara, N., Fuks, H.: Number-conserving cellular automaton rules. Fundamenta Informaticae 50, 2002, 1-13.
• [4] Denker, M., Grillenberger, Ch., Sigmund, K.: Ergodic Theory on Compact Spaces, LNCS 527, Springer-Verlag, Berlin 1976.
• [5] Durand, B., Formenti, E., Róka, Z.: Number-conserving cellular automata 1, Theoretical Computer Science, 209(1-3), 2003,523-535.
• [6] Formenti, E., Grange, A.: Number-conserving cellular automata II: dynamics, Theoretical Computer Science, 304(1-3), 2003,269-290.
• [7] Gacs, P., Kurdyumov. G. L.: Levin, L. A.: One-dimensional uniform arrays that wash out finite islands. Probl. Peredachi Inform., 14, 1978,92-98.
• [8] Gacs, R: Reliable cellular automata with self-organization. J. Stat. Physics 103(1/2), 2001,45-267.
• [9] Gilman, R. H.: Classes of linear automata. Ergod. Th. & Dynam. Sys. 7, 1987, 105-118.
• [10] Grassberger, P.: New mechanism for deterministic diffusion. Physical Review A 28(6), 1983, 3666-3667.
• [11] Kurka, P.: Topological dynamics of cellular automata, Codes, Systems and Graphical Models (B. Marcus and J. Rosenthal, eds.), The IMA Volumes in Mathematics and its Applications, 123, 447-386, Springer-Verlag, Berlin 2001.
• [12] Kůrka, P.: Topological and Symbolic Dynamics, 2003, to be published by Société Mathématique de France.
• [13] Kůrka, P., Maass, A.: Limit sets of cellular automata associated to probability measures. J. Stat. Physics 100(5/6), 2000, 1031-1047.
• [14] Kůrka, P., Maass, A.: Stability of subshifts in cellular automata. Fundamenta Informaticae 52, 2002, 143-155.
• [15] Martin, B.: A group interpretation of particles generated by one dimensional cellular automaton, 54 Wolfram's rule. Research report RR1999-34, ENS Lyon, 1999.
• [16] Mitchell. M., Crutchfield, J. P., Hraber, P. Т.: Evolving cellular automata to perform computations: mechanisms and impediments. Physica D 75, 1994, 361-391.
• [17] Moreira, A., Boceara, N., Goles, E.: On monotone and nearly conservative cellular automata. Discrete Mathematics and Theoretical Computer Science 2003, to appear.
• [18] Pivato, M.: Conservation laws in cellular automata. Nonlinearity, 15, 2002, 1781-1794.
• [19] de Sá, P. G., Maes, C.: The Gacs-Kurdyumov-Levin automaton revisited. J. Stat. Physics, 67(3/4), 1992, 507-522.