Theory of cellular automata: A survey

Albert, 1987, A simple universal cellular automaton and its one-way and totalistic version, Complex Systems, 1, 1 Amoroso, 1972, Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures, J. Comput. System Sci., 6, 448, 10.1016/S0022-0000(72)80013-8 Aso, 1985, Dynamical characteristics of linear cellular automata, J. Comput. System Sci., 30, 291, 10.1016/0022-0000(85)90048-0 Bennett, 1973, Logical reversibility of computation, IBM J. Res. Develop., 6, 525, 10.1147/rd.176.0525 Berger, 1966, The undecidability of the Domino problem, Mem. Amer. Math. Soc., 66 Berlekamp, 1982 Blanchard, 1997, Dynamical properties of expansive one-sided cellular automata, Israel J. Math., 99, 149, 10.1007/BF02760680 Boccara, 2002, Number conserving cellular automaton rules, Fund. Inform., 52, 1 T. Boykett, C. Moore, Conserved quantities in one-dimensional cellular automata, unpublished manuscript, 1998. Burks, 1970, Von Neumann's self-reproducing automata, 3 Cattaneo, 2000, Ergodicity, transitivity, and regularity for linear cellular automata over Zm, Theoret. Comput. Sci., 233, 147, 10.1016/S0304-3975(98)00005-X Choffrut, 1984, On real-time cellular automata and trellis automata, Acta Inform., 21, 393, 10.1007/BF00264617 Chopart, 1998 Codd, 1968 J.H. Conway, unpublished, 1970. Culik II, 1996, An aperiodic set of 13 Wang tiles, Discrete Math., 160, 245, 10.1016/S0012-365X(96)00118-5 Culik II, 1988, Undecidability of CA classification schemes, Complex Systems, 2, 177 Culik II, 1990, Formal languages and global cellular automaton behavior, Physica D, 45, 396, 10.1016/0167-2789(90)90197-W Culik II, 1989, On the limit sets of cellular automata, SIAM J. Comput., 18, 831, 10.1137/0218057 E. Czeizler, J. Kari, A tight linear bound on the neighborhood of inverse cellular automata, to appear. Devaney, 1989 Durand, 1998, Global properties of 2D cellular automata B. Durand, E. Formenti, G. Varouchas, On undecidability of equicontinuity classification for cellular automata, in: M. Morvan, E. Remila (Eds.), Discrete Mathematics and Theoretical Computer Science Proceedings AB, 2003, pp. 117–128. Durand-Lose, 2001, Representing reversible cellular automata with reversible block cellular automata, 145 Dyer, 1980, One-way bounded cellular automata, Inform. Control, 44, 261, 10.1016/S0019-9958(80)90164-3 Finelli, 1998, Luapunov exponents vs expansivity and sensitivity in cellular automata, J. Complexity, 14, 210, 10.1006/jcom.1998.0474 Frisch, 1986, Lattice-gas automata for the Navier–Stokes equation, Phys. Rev. Lett., 56, 1505, 10.1103/PhysRevLett.56.1505 Gacs, 1986, Reliable computation with cellular automata, J. Comput. Systems Sci., 32, 15, 10.1016/0022-0000(86)90002-4 Gardner, 1970, Mathematical games, Sci. Amer., 223–225 Garzon, 1995 Hardy, 1976, Molecular dynamics of a classical lattice gas, Phys. Rev. A, 13, 1949, 10.1103/PhysRevA.13.1949 Hattori, 1991, Additive conserved quantities in discrete-time lattice dynamical systems, Physica D, 49, 295, 10.1016/0167-2789(91)90150-8 Hedlund, 1969, Endomorphisms and automorphisms of shift dynamical systems, Math. Systems Theory, 3, 320, 10.1007/BF01691062 Hurd, 1987, Formal language characterizations of cellular automaton limit sets, Complex Systems, 1, 69 Hurd, 1992, The topological entropy of cellular automata is uncomputable, Ercodic Theory Dynamical Systems, 12, 255, 10.1017/S0143385700006738 Ibarra, 1988, Relating the power of cellular arrays to their closure properties, Theoret. Comput. Sci., 57, 225, 10.1016/0304-3975(88)90040-0 Ito, 1983, Linear Cellular Automata over Zm, J. Comput. System Sci., 27, 125, 10.1016/0022-0000(83)90033-8 Kari, 1990, Reversibility of 2D cellular automata is undecidable, Physica D, 45, 379, 10.1016/0167-2789(90)90195-U Kari, 1992, On the inverse neighborhoods of reversible cellular automata, 477 Kari, 1992, The nilpotency problem of one-dimensional cellular automata, SIAM J. Comput., 21, 571, 10.1137/0221036 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 sets of cellular automata, Theoret. Comput. Sci., 127, 229, 10.1016/0304-3975(94)90041-8 Kari, 1996, Representation of reversible cellular automata with block permutations, Math. Systems Theory, 29, 47, 10.1007/BF01201813 Kari, 1996, A small aperiodic set of Wang tiles, Discrete Math., 160, 259, 10.1016/0012-365X(95)00120-L Kari, 1999, On the circuit depth of structurally reversible cellular automata, Fund. Inform., 38, 93, 10.3233/FI-1999-381208 J. Kari, Linear cellular automata with multiple state variables, in: Proc. STACS’2000, 17th Annu. Symp. on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, Vol. 1770, Springer, Berlin, 2000, pp. 110–121. Kasami, 1968, Some results on capabilities of one-dimensional iterative logical networks, Electron. Comm. Japan, 51-C, 167 Kurka, 1997, Languages equicontinuity and attractors in cellular automata, Ergodic Theory Dynamical Systems, 17, 417, 10.1017/S014338579706985X Manzini, 1998, Invertible linear cellular automata over Zm, J. Comput. System Sci., 56, 60, 10.1006/jcss.1997.1535 Manzini, 1999, A complete and efficiently computable topological classification of D-dimensional linear cellular automata over Zm, Theoret. Comput. Sci., 221, 157, 10.1016/S0304-3975(99)00031-6 Margolus, 1984, Physics-like models of computation, Physica D, 10, 81, 10.1016/0167-2789(84)90252-5 Mazoyer, 1987, A six states minimal time solution to the firing squad synchronization problem, Theoret. Comput. Sci., 50, 183, 10.1016/0304-3975(87)90124-1 Moore, 1962, Machine models of self-reproduction, Proc. Symp. in Applied Mathematics, 14, 17, 10.1090/psapm/014/9961 Morita, 1989, Computation Universality of one dimensional reversible injective cellular automata, IEICE Trans. E, 72, 758 Myhill, 1963, The converse to Moore's Garden-of-Eden theorem, Proc. Amer. Math. Soc., 14, 685 N. Ollinger, The quest for small universal cellular automata, in: Proc. of ICALP 2002, 29th Internat. Colloq. on Automata, Languages and Programming, Lecture Notes in Computer Science, Vol. 2380, Springer, Berlin, 2002, pp. 318–329. Richardson, 1972, Tessellation with local transformations, J. Comput. System Sci., 6, 373, 10.1016/S0022-0000(72)80009-6 Robinson, 1971, Undecidability and nonperiodicity for tilings of the plane, Invent. Math., 12, 177, 10.1007/BF01418780 Sato, 1993, Decidability of some problems of linear cellular automata over finite commutative rings, Inform. Process. Lett., 46, 151, 10.1016/0020-0190(93)90061-D Shereshevsky, 1993, Expansiveness, entropy and polynomial growth for groups acting on subshifts by automorphisms, Indag. Math., 4, 203, 10.1016/0019-3577(93)90040-6 Smith, 1972, Real-time language recognition by one-dimensional cellular automata, J. Comput. System Sci., 6, 233, 10.1016/S0022-0000(72)80004-7 Sutner, 1991, De Bruijn graphs and linear cellular automata, Complex Systems, 5, 19 Takesue, 1995, Staggered invariants in cellular automata, Complex Systems, 9, 149 Terrier, 1995, On real time one-way cellular array, Theoret. Comput. Sci., 141, 331, 10.1016/0304-3975(94)00212-2 Toffoli, 1977, Computation and construction universality of reversible cellular automata, J. Comput. System Sci., 15, 213, 10.1016/S0022-0000(77)80007-X Toffoli, 1987 Toffoli, 1990, Invertible cellular automata, Physica D, 45, 229, 10.1016/0167-2789(90)90185-R Vichniac, 1984, Simulating physics with cellular automata, Physica D, 10, 96, 10.1016/0167-2789(84)90253-7 vonNeumann, 1966 Wang, 1961, Proving theorems by pattern recognition—II, Bell System Tech. J., 40, 1, 10.1002/j.1538-7305.1961.tb03975.x J. Watrous, On one-dimensional quantum cellular automata, in: Proc. of the 36th Annu. Symp. on Foundations of Computer Science, IEEE, New York, 1995, pp. 528–537. Witten, 1983, Diffusion-limited aggregation, Phys. Rev. B, 27, 5686, 10.1103/PhysRevB.27.5686 Wolfram, 1983, Statistical mechanics of cellular automata, Rev. Mod. Phys., 55, 601, 10.1103/RevModPhys.55.601 Wolfram, 1984, Universality and complexity in cellular automata, Physica, 10 D, 1 S. Wolfram (Ed.), Theory and Applications of Cellular Automata, World Scientific Press, Singapore, 1986. Wolfram, 2002