Number-conserving cellular automata I: decidability

Boccara, 1998, Cellular automaton rules conserving the number of active sites, J. Phys. A, 31, 6007, 10.1088/0305-4470/31/28/014 N. Boccara, H. Fukś, Number-conserving cellular automaton rules, Fund. Inform., 2002, to appear. J. Cervelle, B. Durand, Tilings: recursivity and regularity, in: STACS’00, Lecture Notes in Computer Science, Vol. 1770, Springer, Berlin, 2000. Durand, 1994, The surjectivity problem for 2D cellular automata, J. Comput. Systems Sci., 49, 718, 10.1016/S0022-0000(05)80077-7 E. Formenti, A. Grange, Number conserving cellular automata II: dynamics, 2001, submitted for publication. 1990 Hedlund, 1969, Endomorphism and automorphism of the shift dynamical system, Math. System Theory, 3, 320, 10.1007/BF01691062 Kari, 1994, Reversibility and surjectivity problems of cellular automata, J. Comput. System Sci., 48, 149, 10.1016/S0022-0000(05)80025-X Kari, 1994, Rice's theorem for the limit set of cellular automata, Theoret. Comput. Sci., 127, 229, 10.1016/0304-3975(94)90041-8 K. Morita, K. Imai, Number-conserving reversible cellular automata and their computation universality, in: Satellite Workshop on Cellular Automata MFCS’98, 1998, pp. 51–68. K. Morita, Y. Tojima, K. Imai, A simple computer embedded in a reversible and number-conserving 2D cellular space, in: Proc. LA Symp.’99, 1999. 1993 Nagel, 1992, A cellular automaton for freeway traffic, J. Phys. I, 2, 2221 R. Serra, S. Bandini, F. Suggi Liverani (Eds.), Cellular automata: research towards industry, in: Third Conf. on Cellular Automata for Research and Industry, Springer, Heidelberg, 1998. Takesue, 1995, Staggered invariants in cellular automata, Complex Systems, 9, 149 G. Vichniac, P. Manneville, N. Boccara, R. Bidaux (Eds.), Cellular automata and modeling of complex systems, in: Workshop Les Houches, Springer, Heidelberg, 1989. Wolfram, 1986