Palash Sarkar
Skip Abstract Section
Abstract
Cellular automata are simple models of computation which exhibit fascinatingly complex behavior. They have captured the attention of several generations of researchers, leading to an extensive body of work. Here we trace a history of cellular automata from their beginnings with von Neumann to the present day. The emphasis is mainly on topics closer to computer science and mathematics rather than physics, biology or other applications. The work should be of interest to both new entrants into the field as well as researchers working on particular aspects of cellular automata.
- ADAMI, C. 1994. On modeling life. Artif. Life 1, 4 (Summer 1994), 429-438.]]Google Scholar
Cross Ref
- AIGRAIN, P. AND BEAUQUIER, D. 1995. Polyomino tilings, cellular automata and codicity. Theor. Comput. Sci. 147, 1-2 (Aug. 7, 1995), 165-180.]] Google ScholarDigital Library
- ALADYEV, V. 1974. Survey of research in the theory of homogeneous structures and their applications. Math. Biosci. 15, 121-154.]]Google ScholarCross Ref
- AMOROSO, S. AND COOPER, G. 1971. Tessellation structures for reproduction of arbitrary patterns. J. Comput. Syst. Sci. 5, 455-464.]]Google ScholarDigital Library
- AMOROSO, S. AND PATT, Y. 1972. Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures. J. Comput. Syst. Sci. 6, 448-464.]]Google ScholarDigital Library
- ARBIB, M. 1966. Simple self-reproducing universal automata. Inf. Control 9, 177-189.]]Google ScholarCross Ref
- Aso, H. AND HONDA, N. 1985. Dynamical characteristics of linear cellular automata. J. Comput. Syst. Sci. 30, 291-317.]]Google ScholarCross Ref
- BANKS, E. 1970. Cellular automata. AI Memo 198. MIT Artificial Intelligence Laboratory, Cambridge, MA.]]Google Scholar
- BARDELL, P. 1990. Analysis of cellular automata used as pseudorandom pattern generators. In Proceedings of the on IEEE International Test Conference, IEEE Press, Piscataway, NJ, 762-768.]]Google ScholarCross Ref
- BARUA, R. AND RAMAKRISHNAN, S. 1996. ~ -Game, ~+-game and two-dimensional additive cellular automata. Theor. Comput. Sci. 154, 2, 349-366.]] Google ScholarDigital Library
- BLANCHARD, F., KURKA, P., AND MAASS, A. 1997. Topological and measure-theoretic properties of one-dimensional cellular automata. Physica D 103, 1-4, 86-99.]] Google ScholarDigital Library
- BRAGA, G., CATTANEO, G., FLOCCHINI, P., AND VO- GLIOTTI, C.Q. 1995. Pattern growth in elementary cellular automata. Theor. Comput. Sci. 145, 1-2 (July 10, 1995), 1-26.]] Google ScholarDigital Library
- BURKE, A., Ed. 1970. Essays on Cellular Automata. University of Illinois Press, Champaign, IL.]]Google Scholar
- BUTLER, J.T. 1974. A note on cellular automata simulations. Inf. Control 3, 286-295.]]Google ScholarCross Ref
- CHANG, J. H., IBARRA, O. H., AND VERGIS, A. 1988. On the power of one-way communication. J. ACM 35, 3 (July 1988), 697-726.]] Google ScholarDigital Library
- CHAUDHURI, P. E. AL. 1997. Additive Cellular Automata Theory and Applications. Vol. 1. IEEE Press advances in circuits and systerns series. IEEE Press, Piscataway, NJ.]]Google Scholar
- CHOFFRUT, C AND CULIK, K 1984. On real-time cellular automata and trellis automata. Acta Inf. 21, 4 (Nov. 1984), 393-407.]] Google ScholarDigital Library
- CHUA, L. AND YANG, L. 1988. Cellular neural networks: Theory and applications. IEEE Trans. Circ. Syst., 1257-1290.]]Google ScholarCross Ref
- CODD, E. 1968. Cellular Automata. Academic Press, Inc., New York, NY.]] Google ScholarDigital Library
- COLE, S. 1969. Real-time computation by n-dimensional iterative arrays of finite state machine. IEEE Trans. Comput. 18, 349-365.]]Google ScholarDigital Library
- CONWAY, J., GuY, R., AND BERLEKAMP, E. 1992. Winning Ways: For Your Mathematical Plays, vol. 2.]]Google Scholar
- CULIK II, K. 1987. On invertible cellular automata. Complex Syst. 1, 1035-1044.]]Google Scholar
- CULIK II, K. 1989. Variations of the firing squad problem and applications. Inf. Process. Lett. 30, 3 (Feb. 1989), 153-157.]] Google ScholarDigital Library
- CULIK II, K. AND DUBE, S. 1991. An efficient solution of the firing mob problem. Theor. Comput. Sci. 91, 1 (Dec. 9, 1991), 57-69.]] Google ScholarDigital Library
- CULIK II, K, GRUSKA, J, AND SALOMAA, A 1986. Systolic trellis automata: Stability, decidability and complexity. Inf. Control 71, 3 (Dec. 1986), 218-230.]] Google ScholarDigital Library
- CULIK, K., HURD, L. P., AND YU, S. 1990. Computation theoretic aspects of cellular automata. Physica D 45, 1-3 (Sep. 1990), 357- 378.]] Google ScholarDigital Library
- CULIK, K., PACHL, J., AND YU, S. 1989. On the limit sets of cellular automata. SIAM J. Comput. 18, 4 (Aug. 1989), 831-842.]] Google ScholarDigital Library
- CULIK II, K. AND YU, S. 1988. Undecidability of CA classification schemes. Complex Syst. 2, 2 (Apr., 1988), 177-190.]] Google ScholarDigital Library
- CULIK, K. AND YU, S. 1991. Cellular automata, ~o~o-regular sets, and sofic systems. Discrete Appl. Math. 32, 2 (July 1991), 85-101.]] Google ScholarDigital Library
- DUBACQ, J. 1995. How to simulate Turing machines by invertible one-dimensional cellular automata. Int. J. Foundations Comput. Sci. 6, 4, 395-402.]]Google ScholarCross Ref
- DURAND, B. 1994. Inversion of 2D cellular automata: some complexity results. Theor. Comput. Sci. 134, 2 (Nov. 21, 1994), 387-401.]] Google ScholarDigital Library
- DURAND, B. 1995. A random NP-complete problem for inversion of 2D cellular automata. Theor. Comput. Sci. 148, 1 (Aug. 21, 1995), 19-32.]] Google ScholarDigital Library
- DYER, C. 1980. One-way bounded cellular automata. Inf. Control 44, 261-281.]]Google ScholarCross Ref
- FINELLI, M., MANZINI, G., AND MARGARA, L. 1998. Lyapunov exponents versus expansivity and sensitivity in cellular automata. J. Complexity 14, 2, 210-233.]] Google ScholarDigital Library
- G cs, P. 1986. Reliable computation with cellular automata. J. Comput. Syst. Sci. 32, 1 (Feb. 1986), 15-78.]] Google ScholarDigital Library
- GACS, P. 1997. Reliable cellular automata with self-organization. In Proceedings of the Conference on Foundations of Computer Science,]] Google ScholarDigital Library
- GARDNER, M. 1970. The fantastic combinations of John Conway's new solitaire game "Life". Sci. Am. 223, 120-123.]]Google Scholar
- GARDNER, M. 1971. On cellular automata, selfreproduction, the Garden of Eden and the game of "Life". Sci. Am. 224, 112-117.]]Google Scholar
- GARZON, M. 1995. Models of Massive Parallelism: Analysis of Cellular Automata and Neural Networks. EATCS monographs on theoretical computer science. Springer-Verlag, Berlin, Germany.]] Google ScholarDigital Library
- GOLZE, U. 1976. Differences between 1- and 2-dimensional cell spaces. In Automata, Languages, Development. North-Holland Publishing Co., Amsterdam, The Netherlands, 369 -384.]]Google Scholar
- GREEN, F. 1987. NP-complete problems in cellular automata. Complex Syst. 1,453-474.]]Google Scholar
- GUAN, P. AND HE, Y. 1986. Exact results for deterministic cellular automata with additive rules. J. Stat. Phys. 43, 463-478.]]Google ScholarCross Ref
- HAMACHER, V. 1971. Machine complexity versus interconnection complexity in iterative arrays. IEEE Trans. Comput. C-20 (Apr.), 321-323.]]Google ScholarDigital Library
- HARAO, M. AND NOGUCHI, S. 1975. Fault tolerant cellular automata. J. Comput. Syst. Sci. 11, 171-185.]]Google ScholarDigital Library
- HARAO, M. AND NOGUCHI, S. 1978. On some dynamical properties of finite cellular automata. IEEE Trans. Comput. 27, 1.]]Google Scholar
- HEDLUND, G. 1969. Endomorphisms and automorphisms of the shift dynamical systems. Math. Syst. Theory 4, 3, 320-375.]]Google ScholarCross Ref
- HERMAN, G. 1974. Synchronization of growing cellular arrays. Inf. Control 25, 2, 103-122.]]Google ScholarCross Ref
- HOLLAND, J. 1976.Studies of the spontaneous emergence of self-replicating systems using cellular automata and formal grammers. In Automata, Languages, Development. North- Holland Publishing Co., Amsterdam, The Netherlands, 385-404.]]Google Scholar
- HURD, L. 1987. Formal language characterizations of cellular automata limit sets. Complex Syst. 1, 69-80.]]Google Scholar
- HURD, L., KARI, J., AND CULIK II, K. 1992. The topological entropy of cellular automata is uncomputable. Ergodic Theor. Dynamic. Syst. 12, 255-265.]]Google ScholarCross Ref
- IBARRA, O. H. AND JIANG, T. 1987. On one-way cellular arrays. SIAM J. Comput. 16, 6 (Dec. 1, 1987), 1135-1154.]] Google ScholarDigital Library
- IBARRA, O. AND KIM, S. 1984. Characterizations and computational complexity of systolic trellis automata. Theor. Comput. Sci. 29, 123- 153.]]Google ScholarCross Ref
- IBARRA, O. H., PALIS, M. A., AND KIM, S.M. 1985. Fast parallel language recognition by cellular automata. Theor. Comput. Sci. 41, 2,3 (Mar. 1985), 231-246.]] Google ScholarDigital Library
- IBARRA, O., PALIS, M., AND KIM, S. 1985. Some results concerning linear iterative (systolic) arrays. J. Parallel Distrib. Comput. 2, 182- 218.]]Google ScholarCross Ref
- IKEGAMI, T. AND HASHIMOTO, T. 1995. Active mutation in self-reproducing networks of machines and tapes. Artif. Life 2, 3, 305-318.]]Google ScholarDigital Library
- ITO, M., OSATO, N., AND NASU, M. 1983. Linear cellular automata over Zm. J. Comput. Syst. Sci. 27, 125-140.]]Google ScholarCross Ref
- JEN, M. 1988. Linear cellular automata and recurring sequences in finite fields. Commun. Math. Phys. 119, 13-28.]]Google ScholarCross Ref
- JUMP, J. AND KIRTANE, J. 1974. On the interconnection structure of cellular networks. Inf. Control 24, 74-91.]]Google ScholarCross Ref
- KARI, J. 1990. Reversibility of 2D cellular automata is undecidable. In Cellular Automata: Theory and Experiment, H. Gutowitz, Ed. MIT Press, Cambridge, MA, 379-385.]] Google ScholarDigital Library
- KARI, J. 1992. The nilpotency problem of onedimensional cellular automata. SIAM J. Comput. 21, 3 (June 1992), 571-586.]] Google ScholarDigital Library
- KARI, J. 1994. Reversibility and surjectivity problems of cellular automata. J. Comput. Syst. Sci. 48, 1 (Feb. 1994), 149-182.]] Google ScholarDigital Library
- KARI, L., ROZENBERG, G., AND SALOMAA, A. 1997. L systems. In Handbook of Formal Languages, vol. 1: Word, Language, Grammar, G. Rozenberg and A. Salomaa, Eds. Springer- Verlag, New York, NY, 253-328.]] Google ScholarDigital Library
- KAWAHARA, Y. ET AL. 1995. Period lengths of cellular automata on square lattices with rule 90. J. Math. Phys. 36, 3, 1435-1456.]]Google ScholarCross Ref
- KNUTH, D. E. 1997. The Art of Computer Programming, Volume 2: Seminumerical Algorithms. 3rd ed. Addison-Wesley Longman Publ. Co., Inc., Reading, MA.]] Google ScholarDigital Library
- KOSARAJU, S. R. 1975. Speed of recognition of context-free languages by array automata. SIAM J. Comput. 4, 3 (Sept.), 331-340.]]Google ScholarCross Ref
- KUNG, S. Y. 1987. VLSI Array Processors. Prentice-Hall information and system sciences series. Prentice-Hall, Inc., Upper Saddle River, NJ.]] Google ScholarDigital Library
- KURKA, P. 1997. Languages, equicontinuity and attractors in cellular automata. Ergodic Theor. Dynamic. Syst. 17, 229-254.]]Google Scholar
- LANGTON, C. 1984. Self-reproduction in cellular automata. Physica D 10, 134-144.]]Google ScholarCross Ref
- LE BRUYN, L. AND VAN DEN BERGH, M. 1991. Algebraic properties of linear cellular automata. Linear Alg. Appl. 157, 217-234.]]Google ScholarCross Ref
- LEE, H. AND KAWAHARA, Y. 1996. Transition diagrams of finite cellular automata. Bull. Inf. Cybern. 28, 1.]]Google Scholar
- LINDENMAYER, A. 1968. Mathematical models for cellular interactions in development, parts I and II. J. Theor. Biol. 18, 280-315.]]Google ScholarCross Ref
- LITOW, B. AND DUMAS, PH. 1993. Additive cellular automata and algebraic series. Theor. Comput. Sci. 119, 2 (Oct. 25, 1993), 345-354.]] Google ScholarDigital Library
- MACH, A. AND MIGNOSI, F. 1993. Garden of Eden configurations for cellular automata on Cayley graphs of groups. SIAM J. Discrete Math. 6, 1 (Feb. 1993), 44-56.]] Google ScholarDigital Library
- MAHAJAN, M. 1992. Studies in language classes defined by different types of time-varying cellular automata. Ph.D. Dissertation.]]Google Scholar
- MANZINI, G. AND MARGARA, L. 1999. Attractors of linear cellular automata. J. Comput. Syst. Sci. .]] Google ScholarDigital Library
- MANZINI, G. AND MARGARA, L. 1998. Invertible linear cellular automata over Zm :Algorithmic and dynamical aspects. J. Comput. Syst. Sci. 56, 1, 60-67.]] Google ScholarDigital Library
- MARTIN, B. 1994. A universal cellular automata in quasi-linear time and its S-m-n form. Theor. Comput. Sci. 123, 2 (Jan. 31, 1994), 199-237.]] Google ScholarDigital Library
- MARTIN, O., ODLYZKO, A., AND WOLFRAM, S. 1984. Algebraic properties of cellular automata. Commun. Math. Phys. 93, 219-258.]]Google ScholarCross Ref
- MARUOKA, A. AND KIMURA, M. 1974. Completeness problem of one-dimensional binary scope-3 tessellation automata. J. Comput. Syst. Sci. 9, 1, 31-47.]]Google ScholarDigital Library
- MARUOKA, A. AND KIMURA, M. 1977. Completeness problem of multi-dimensional tessellation automata. Inf. Control 35, 1, 52- 86.]]Google ScholarCross Ref
- MAZOYER, J. 1987. A six-state minimal time solution to the firing squad synchronization problem. Theor. Comput. Sci. 50, 2 (Sept. 1987), 183-238.]] Google ScholarDigital Library
- MAZOYER, J. AND REIMEN, N. 1992. A linear speed-up theorem for cellular automata. Theor. Comput. Sci. 101, 1 (July 13, 1992), 59-98.]] Google ScholarDigital Library
- MICHELE, D., MANZINI, G., AND MARGARA, L. 1988. On computing the entropy of cellular automata. In Proceedings of the 13th International Colloquium on Automata, Languages and Programming (Rennes, France, July), L. Kott, Ed. Elsevier Sci. Pub. B. V., Amsterdam, The Netherlands.]] Google ScholarDigital Library
- MITCHELL, M., CRUTCHFIELD, J. P., AND HRABER, P. T. 1994. Evolving cellular automata to perform computations: mechanisms and impediments. Physica D 75, 1-3 (Aug. 1, 1994), 361-391.]] Google ScholarDigital Library
- MOORE, E., Ed. 1964. Sequential Machines. Selected Papers. Addison-Wesley Publishing Co., Inc., Redwood City, CA.]] Google ScholarDigital Library
- MOORE, E. AND LANGDON, G. 1968. A generalized firing squad problem. Inf. Control 12, 212-220.]]Google ScholarCross Ref
- MORITA, K. 1992. Computation-universality of one-dimensional one-way reversible cellular automata. Inf. Process. Lett. 42, 6 (July 24, 1992), 325-329.]] Google ScholarDigital Library
- MORITA, K. 1995. Reversible simulation of onedimensional irreversible cellular automata. Theor. Comput. Sci. 148, 1 (Aug. 21, 1995), 157-163.]] Google ScholarDigital Library
- MYHILL, J. 1963. The converse of Moore's Garden-of-Eden theorem. Proc. Am. Math. Soc. 14, 685-686.]]Google Scholar
- NANDI, S. AND CHAUDHURI, P.P. 1996. Analysis of periodic and intermediate boundary 90/150 cellular automata. IEEE Trans. Comput. 45, 1, 1-12.]] Google ScholarDigital Library
- NANDI, S., KAR, B., AND PAL CHAUDHARI, P. 1994. Theory and applications of cellular automata in cryptography. IEEE Trans. Comput. 43, 12 (Dec. 1994).]] Google ScholarDigital Library
- NGUYEN, H. AND HAMACHER, V. 1974. Pattern synchronization in two-dimensional cellular spaces. Inf. Control 26, 12-23.]]Google ScholarCross Ref
- NIEMI, V. 1997. Cryptology: language-theoretic aspects. In Handbook of Formal Languages, vol. 2: Linear Modeling: Background and Application, G. Rozenberg and A. Salomaa, Eds. Springer-Verlag, New York, NY, 507-524.]] Google ScholarDigital Library
- NISHIO, H. AND KOBUCHI, Y. 1975. Fault tolerant cellular spaces. J. Comput. Syst. Sci. 11, 150-170.]]Google ScholarDigital Library
- OSTRAND, T. 1971. Pattern recognition in tessellation automata of arbitrary dimensions. J. Comput. Syst. Sci. 5, 623-628.]]Google ScholarDigital Library
- PACKARD, N. 1985. Two-dimensional cellular automata. J. Stat. Phys. 30, 901-942.]]Google ScholarCross Ref
- PELLETIER, D. H. 1987. Merlin's magic square. Am. Math. Monthly 94, 2 (Feb. 1987), 143-150.]] Google ScholarDigital Library
- PESAVENTO, U. 1995. An implementation ofvon Neumann's self-reproducing machine. Artif. Life 2, 4, 337-354.]]Google ScholarDigital Library
- PIGHIZZINI, a. 1994. Asynchronous automata versus asynchronous cellular automata. Theor. Comput. Sci. 132, 1-2 (Sept. 26, 1994), 179-207.]]Google ScholarCross Ref
- PRUSINKIEWICZ, P. AND LINDENMAYER, A. 1990. The Algorithmic Beauty of Plants. Springer- Verlag, New York, NY.]] Google ScholarDigital Library
- RICHARDSON, D. 1972. Tessellations with local transformations. J. Comput. Syst. Sci. 6, 373-388.]]Google ScholarDigital Library
- RICHTER, S. AND WERNER, R. 1996. Ergodicity of quantum cellular automata. J. Stat. Phys. 82, 963-998.]]Google ScholarCross Ref
- R KA, Z. 1994. One-way cellular automata on Cayley graphs. Theor. Comput. Sci. 132, 1-2 (Sept. 26, 1994), 259-290.]]Google Scholar
- RoKA, Z. 1995. The firing squad synchronization problem on Cayley graphs. In Proceedings of the Conference on MFCS, Lecture Notes in Computer Science Springer-Verlag, New York, 402-411.]] Google ScholarDigital Library
- SARKAR, P. 1996. ~+-automata on square grids. Complex Syst. 10, 121-141.]]Google Scholar
- SARKAR, P. AND BARUA, R. 1998a. Multidimensional ~-automata, ~-polynomials and generalised S-matrices. Theor. Comput. Sci. 197, 1-2, 111-138.]] Google ScholarDigital Library
- SARKAR, P. AND BARUA, R. 1998b. The set of reversible 90/150 cellular automata is regular. Discrete Appl. Math. 84, 1-3, 199-213.]] Google ScholarDigital Library
- SATO, T. 1994. Group structured linear cellular automata over Zm. J. Comput. Syst. Sci. 49, 1 (Aug. 1994), 18-23.]] Google ScholarDigital Library
- SEIFERAS, J. 1982. Observations on nondeterministic multidimensional iterative arrays. In Proceedings of the ACM Symposium on the Theory of Computing, ACM Press, New York, NY, 276-289.]] Google ScholarDigital Library
- SERRA, M. ET AL. 1990. The analysis of onedimensional cellular automata and their aliasing properties. IEEE Trans. CAD/ICAS 9, 7, 767-778.]]Google ScholarDigital Library
- SERRA, M. AND SLATER, T. 1990. A Lanczos algorithm in a finite field and its applications. J. Comb. Math. Comb. Comp..]]Google Scholar
- SHERESHEVSKY, M. 1992. Lyapunov exponents for one-dimensional cellular automata. J. Nonlinear Sci. 2, 1-8.]]Google ScholarCross Ref
- SHINAHR, I. 1974. Two- and three-dimensional firing-squad synchronization problems. Inf. Control 24, 163-180.]]Google ScholarCross Ref
- SMITH III, A. 1971. Cellular automata complexity trade-offs. Inf. Control 18, 466-482.]]Google ScholarCross Ref
- SMITH III, A. 1972. Real-time language recognition by one-dimensional cellular automata. J. Comput. Syst. Sci. 6, 233-253.]]Google ScholarDigital Library
- SMITH III, A. 1976. Introduction to and survey of polyautomata theory. In Automata, Languages, Development. North-Holland Publishing Co., Amsterdam, The Netherlands.]]Google Scholar
- SOMMERHALDER, R. AND WESTRHENEN, S.V. 1983. Parallel language recognition in constant time by cellular automata. Acta Inf. 19, 397- 407.]] Google ScholarDigital Library
- SUTNER, K. 1988a. Additive automata on graphs. Complex Syst. 2, 6 (Dec. 1988), 649-661.]] Google ScholarDigital Library
- SUTNER, K. 1988b. On ~-automata. Complex Syst. 2, 1 (Feb, 1988), 1-28.]] Google ScholarDigital Library
- SUTNER, K. 1989a. The computation complexity of cellular automata. In Fundamentals of Computation Theory Lecture Notes in Computer Science. Springer-Verlag, New York, 451-459.]] Google ScholarDigital Library
- SUTNER, K. 1989b. Linear cellular automata and the Garden-of-Eden. Math. Intell. 11, 2, 49-53.]]Google ScholarCross Ref
- SUTNER, K. 1989c. A note on the Culik-Yu classes. Complex Syst. 3, 1, 107-115.]]Google Scholar
- SUTNER, K. 1990a. Classifying circular cellular automata. Physica D 45, 1-3 (Sep. 1990), 386 -395.]] Google ScholarDigital Library
- SUTNER, K. 1990b. The ~-game and cellular automata. Am. Math. Monthly 97, 1 (Jan. 1990), 24-34.]] Google ScholarDigital Library
- SUTNER, K. 1991. De Bruijn graphs and linear cellular automata. Complex Syst. 5, 19-30.]]Google Scholar
- SUTNER, K. 1995. On the computational complexity of finite cellular automata. J. Comput. Syst. Sci. 50, 1 (Feb. 1995), 87-97.]] Google ScholarDigital Library
- SUTNER, K. 1999. ~-automata and Chebyshevpolynomials. Theor. Comput. Sci..]] Google ScholarDigital Library
- TAKAHASHI, S. 1992. Self-similarity of linear cellular automata. J. Comput. Syst. Sci. 44, 1 (Feb. 1992), 114-140.]] Google ScholarDigital Library
- TERRIER, V. 1996. Language not recognizable in real time by one-way cellular automata. Theor. Comput. Sci. 156, 1-2, 281-287.]] Google ScholarDigital Library
- TEZUKA, S. AND FUSHIMI, M. 1994. A method of designing cellular automata as pseudorandom number generators for built-in self-test for VLSI. In Finite Fields: Theory, Applications, and Algorithms Contemporary Mathematics: Cont. Math.. AMS, Providence, RI, 363- 367.]]Google Scholar
- TOFFOLI, T. 1977. Computation and construction universality of reversible cellular automata. J. Comput. Syst. Sci. 15, 213-231.]]Google ScholarCross Ref
- TOFFOLI, T. AND MARGOLUS, N. 1990. Invertible cellular automata: a review. Physica D 45, 1-3 (Sep. 1990), 229-253.]] Google ScholarDigital Library
- VARSHAVSKY, V., MARAKHOVSKY, V., AND PECHAN- SKY, V. 1969. Synchronization of interacting automata. Math. Syst. Theory 4, 3, 212-230.]]Google Scholar
- VITANYI, P. 1973. Sexually reproducing cellular automata. Math. Biosci. 18, 23-54.]]Google ScholarCross Ref
- VOLLMAR, T. 1977. Cellular spaces and parallel algorithms, an introductory survey. In Parallel Computation-Parallel Mathematics, M. Feilmeier, Ed. North-Holland Publishing Co., Amsterdam, The Netherlands, 49-58.]]Google Scholar
- VON NEUMANN, J. 1963a. The general and logical theory of automata. In J. von Neumann Collected Works, A. Taub, Ed.]]Google Scholar
- VON NEUMANN, J. 1963b. Probabilistic logics and the synthesis of reliable organisms from unreliable components. In J. von Neumann Collected Works, A. Taub, Ed.]]Google Scholar
- VON NEUMANN, J. AND BURKS, A. W., Eds, 1966. Theory of Self-Reproducing Automata. University of Illinois Press, Champaign, IL.]] Google ScholarDigital Library
- WAKSMAN, A. 1966. An optimum solution to the firing squad synchronization problem. Inf. Control 9, 67-78.]]Google ScholarCross Ref
- WATROUS, J. 1996. On one-dimensional quanturn cellular automata. In Proceedings of the 37th IEEE Symposium on Foundations of Computer Science (FOCS '96), IEEE Computer Society Press, Los Alamitos, CA, 528- 537.]] Google ScholarDigital Library
- WILLSON, S. 1978. On convergence ofconfigurations. Discrete Math. 23, 279-300.]]Google ScholarCross Ref
- WILLSON, S. 1981. Growth patterns of ordered cellular automata. J. Comput. Syst. Sci. 22, 29-41.]]Google ScholarCross Ref
- WILLSON, S. 1984a. Cellular automata can generate fractals. Discrete Appl. Math. 8, 91-99.]]Google ScholarCross Ref
- WILLSON, S. 1984b. Growth rates and fractional dimensions in cellular automata. Physica D 10, 69-74.]]Google ScholarCross Ref
- WOLFRAM, S. 1983. Statistical mechanics of cellular automata. Rev. Modern Phys. 55, 601- 644.]]Google ScholarCross Ref
- WOLFRAM, S. 1984a. Computation theory of cellular automata. Commun. Math. Phys. 96, 15-57.]]Google ScholarCross Ref
- WOLFRAM, S. 1984b. Universality and complexity in cellular automata. Physica D 10, 1-35.]]Google ScholarCross Ref
- WOLFRAM, S. 1986. Theory and Applications of Cellular Automata: Including Selected Papers 1983-1986. World Scientific Publishing Co., Inc., River Edge, NJ.]]Google Scholar
- YAKU, T. 1973. The constructibility of a configuration in a cellular automata. J. Comput. Syst. Sci. 7, 4, 481-496.]]Google ScholarDigital Library
- YAMADA, H. AND AMOROSO, S. 1969. Tessellation automata. Inf. Control 14, 299-317.]]Google ScholarCross Ref
- YAMADA, H. AND AMOROSO, S. 1970. A completeness problem for pattern generation in tessellation automata. J. Comput. Syst. Sci. 4, 137-176.]]Google ScholarDigital Library
- YAMADA, H. AND AMOROSO, S. 1971. Structural and behavioural equivalences of tessellation automata. Inf. Control 18, 1-31.]]Google ScholarCross Ref
Index Terms
- A brief history of cellular automata
Recommendations
Discovering the rules of a elementary one-dimensional automaton
IDEAL'12: Proceedings of the 13th international conference on Intelligent Data Engineering and Automated LearningIn this work we present a way to find the set of rules for the evolution of a one-dimensional cellular automata through its window of evolution using genetic algorithm, a search routine that mimics the behavior of the genetic evolution of living beings. ...
Closure properties of cellular automata
Concerning the power of one-dimensional cellular automata recognizers, Ibarra and Jiang have proved that real time cellular automata (CA) and linear time CA are equivalent if and only if real time CA is closed under reverse. In this paper we investigate ...
Descriptional complexity of cellular automata and decidability questions
Third international workshop on descriptional complexity of automata, grammars and related structuresWe study the descriptional complexity of cellular automata (CA) which are a parallel model of computation. We show that between one of the simplest cellular models, the realtime one-way CA (realtime-OCA), and "classical" models like deterministic finite ...
Reviews
W. Richard Stark
Sarkar focuses on topics close to the computer science and mathematics—rather than the physics and biology—of cellular automata (CA). This history is organized into three parts: classical themes of von Neumann and Ulam; contributions of Wolfram and others to computational problems; and games, such as Life and s-games. Nevertheless, self-reproduction, Lindenmayer's systems, artificial life, and self-organization are not ignored. These biological topics constitute nearly 20 percent of the paper. Of course, understanding self-reproduction—the problem that led von Neumann and, later, Ulam to develop cellular automata—must be included in any history of the field. The use of Shannon entropies in connection with self-organization is mentioned on page 94. However, the even stronger equivalence between non-ergodic global-state transformations and self-organization is not mentioned. Also, Sarkar does not cover nondeterministic or asynchronous cellular automata. Nondeterminism makes the global state space much more computationally connected and, with control from entropy-reducing cell behavior (mentioned on page 94), can lead to a stronger notion of CA-computability [1]. Computational universality, Wolfram's classification problem, fractal properties of limit-sets of space-time patterns for cellular automata, topological properties, various notions and measures of global dynamics, and computational complexity are covered well. Complexity is addressed for 1-, 2-, and n -dimensional arrays. However, definitions of primary concepts are often confused or missing (see “topological entropy,” p. 99). The paper also has a pervasive vagueness that makes it difficult to understand. Such vagueness, or outright error, occurs in all of the attempts I have seen to present a broad view of this subject. The broad view simply involves too many nontrivial and disparate methods, especially from mathematics, to be easily surveyed. A thorough online bibliography for cellular automata is available at http://alife.santafe.edu/alife/topics/cas/ca-faq/ca-faq.bib, the Web site of the Santa Fe Institute. In addition, this paper contains a bibliography of over 150 references. In spite of a few shortcomings, this limited history stands as an important and valuable resource for the cellular automata research community. I intend to use it in my graduate course on models of distributes information processing.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments