The DOI matches its Crossref record; 58 of the 58 references it cites were found in a registry or an index.
A brief history of cellular automata
Open accessAbstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
The Art of Computer Programming
Knuth, D. E. (1968) · Cited by 16,337
Theory of Self-Reproducing Automata
Schwartz, J. T., von Neumann, J., & Burks, A. W. (1967) · Mathematics of Computation · doi:10.2307/2005041 · Cited by 5,422
Cellular neural networks: theory
Chua, L. O., & Yang, L. (1988) · IEEE Transactions on Circuits and Systems · doi:10.1109/31.7600 · Cited by 4,769
The Art of Computer Programming. Volume 2: Seminumerical Algorithms.
Taussky, O., & Knuth, D. E. (1970) · The American Mathematical Monthly · doi:10.2307/2317055 · Cited by 3,822
Statistical mechanics of cellular automata
Wolfram, S. (1983) · Reviews of Modern Physics · doi:10.1103/revmodphys.55.601 · Cited by 3,114
The Algorithmic Beauty of Plants
Prusinkiewicz, P., & Lindenmayer, A. (1990) · The Virtual Laboratory · doi:10.1007/978-1-4613-8476-2 · Cited by 2,823
Universality and complexity in cellular automata
Wolfram, S. (1984) · Physica D: Nonlinear Phenomena · doi:10.1016/0167-2789(84)90245-8 · Cited by 1,914
Theory and Applications of Cellular Automata
Wolfram, S. (1986) · Cited by 1,743
Probabilistic Logic and the Synthesis of Reliable Organisms from Unreliable Components
von Neumann, J. (1956) · Cited by 1,652
Mathematical models for cellular interactions in development I. Filaments with one-sided inputs
Lindenmayer, A. (1968) · Journal of Theoretical Biology · doi:10.1016/0022-5193(68)90079-9 · Cited by 1,620
Kung, S. (1985) · IEEE ASSP Magazine · doi:10.1109/massp.1985.1163741 · Cited by 1,515
Probabilistic Logics and the Synthesis of Reliable Organisms From Unreliable Components
Neumann, J. V. (1956) · Automata Studies. (AM-34) · doi:10.1515/9781400882618-003 · Cited by 1,456
Winning Ways for Your Mathematical Plays.
Connelly, R., Berlekamp, E. R., Conway, J. H., & Guy, R. K. (1986) · The American Mathematical Monthly · doi:10.2307/2323620 · Cited by 1,433
Codd, E. F. (1968) · Cited by 1,366
Endomorphisms and automorphisms of the shift dynamical system
Hedlund, G. A. (1969) · Theory of Computing Systems · doi:10.1007/bf01691062 · Cited by 1,034
Mazets, E. P., Golenetskii, S. V., Il’Inskii, V. N., Panov, V. N., Aptekar, R. L., Gur’yan, Y. A., Proskura, M. P., Sokolov, I. A., Sokolova, Z. Y., Kharitonova, T. V., et al. (1982) · Catalog of Cosmic Gamma-Ray Bursts from the KONUS Experiment Data · doi:10.1007/978-94-009-7960-4_2 · Cited by 896
Lindenmayer, A. (1968) · Journal of Theoretical Biology · doi:10.1016/0022-5193(68)90080-5 · Cited by 828
The General and Logical Theory of Automata
von Neumann, J. (2017) · doi:10.4324/9781315130569-15 · Cited by 724
Burks, A. W. (1970) · Medical Entomology and Zoology · Cited by 663
Computation theory of cellular automata
Wolfram, S. (1984) · Communications in Mathematical Physics · doi:10.1007/bf01217347 · Cited by 625
Self-reproduction in cellular automata
Langton, C. G. (1984) · Physica D: Nonlinear Phenomena · doi:10.1016/0167-2789(84)90256-2 · Cited by 571
Two-dimensional cellular automata
Packard, N. H., & Wolfram, S. (1985) · Journal of Statistical Physics · doi:10.1007/bf01010423 · Cited by 472
Additive Cellular Automata: Theory and Applications
Chaudhuri, P. P., Chowdhury, D. R., Nandi, S., & Chattopadhyay, S. (1997) · Cited by 471
Algebraic properties of cellular automata
Martin, O., Odlyzko, A. M., & Wolfram, S. (1984) · Communications in Mathematical Physics · doi:10.1007/bf01223745 · Cited by 406
Mathematical Models for Cellular Interactions in Development
Lindenmayer, A. (1968) · Cited by 401
Theory and applications of cellular automata in cryptography
Nandi, S., Kar, B. K., & Chaudhuri, P. P. (1994) · IEEE Transactions on Computers · doi:10.1109/12.338094 · Cited by 392
Invertible cellular automata: A review
Toffoli, T., & Margolus, N. H. (1990) · Physica D: Nonlinear Phenomena · doi:10.1016/0167-2789(90)90185-r · Cited by 376
Evolving cellular automata to perform computations: mechanisms and impediments
Mitchell, M., Crutchfield, J. P., & Hraber, P. T. (1994) · Physica D: Nonlinear Phenomena · doi:10.1016/0167-2789(94)90293-3 · Cited by 353
Two-Dimensional Cellular Automata
Wolfram, S. (2018) · CRC Press eBooks · doi:10.1201/9780429494093-6 · Cited by 311
A calculus for the random generation of labelled combinatorial structures
Flajolet, P., Zimmermann, P., & Cutsem, B. V. (1994) · Theoretical Computer Science · doi:10.1016/0304-3975(94)90226-7 · Cited by 281
Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures
Amoroso, S., & Patt, Y. N. (1972) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(72)80013-8 · Cited by 271
Computation and construction universality of reversible cellular automata
Toffoli, T. (1977) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(77)80007-x · Cited by 210
Real-time language recognition by one-dimensional cellular automata
Smith, A. R. (1972) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(72)80004-7 · Cited by 188
Sequential Machines: Selected Papers
Thatcher, J. W., & Moore, E. F. (1965) · Mathematics of Computation · doi:10.2307/2004143 · Cited by 180
On one-dimensional quantum cellular automata
Watrous, J. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1995.492583 · Cited by 164
Proceedings 44th IEEE Symposium on Foundations of Computer Science - FOCS 2003
(2003) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2003.1238173 · Cited by 161
Reliable computation with cellular automata
Gács, P. (1986) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(86)90002-4 · Cited by 157
Models of Massive Parallelism: Analysis of Cellular Automata and Neural Networks
Garzón, M. (2012) · Cited by 138
An Implementation of von Neumann's Self-Reproducing Machine
Pesavento, U. (1995) · Artificial Life · doi:10.1162/artl.1995.2.337 · Cited by 133
Undecidability of CA Classification Schemes
Čulík, K., & Yü, S. (1988) · Complex Systems · Cited by 129
Cellular automata can generate fractals
Willson, S. J. (1984) · Discrete Applied Mathematics · doi:10.1016/0166-218x(84)90082-9 · Cited by 97
Simple self-reproducing universal automata
Arbib, M. A. (1966) · Information and Control · doi:10.1016/s0019-9958(66)90220-8 · Cited by 82
Reversible simulation of one-dimensional irreversible cellular automata
Morita, K. (1995) · Theoretical Computer Science · doi:10.1016/0304-3975(95)00038-x · Cited by 80
Speed of Recognition of Context-Free Languages by Array Automata
Kosaraju, S. R. (1975) · SIAM Journal on Computing · doi:10.1137/0204028 · Cited by 78
On the Computational Complexity of Finite Cellular Automata
Sutner, K. (1995) · Journal of Computer and System Sciences · doi:10.1006/jcss.1995.1009 · Cited by 69
Self-similarity of linear cellular automata
Takahashi, S. (1992) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(92)90007-6 · Cited by 61
Yamada, H., & Amoroso, S. (1969) · Information and Control · doi:10.1016/s0019-9958(69)90090-4 · Cited by 54
Computation-universality of one-dimensional one-way reversible cellular automata
Morita, K. (1992) · Information Processing Letters · doi:10.1016/0020-0190(92)90231-j · Cited by 53
Ergodicity of quantum cellular automata
Richter, S., & Werner, R. F. (1996) · Journal of Statistical Physics · doi:10.1007/bf02179798 · Cited by 51
On the power of one-way communication
Chang, J. H., Ibarra, Ó. H., & Vergis, A. (1988) · Journal of the ACM · doi:10.1145/44483.44493 · Cited by 48
Fault tolerant cellular automata
Harao, M., & Noguchi, S. (1975) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(75)80066-3 · Cited by 38
Sexually reproducing cellular automata
Vitanyi, P. M. B. (1973) · Mathematical Biosciences · doi:10.1016/0025-5564(73)90018-7 · Cited by 37
Fast parallel language recognition by cellular automata
Ibarra, Ó. H., Palis, M. A., & Kim, S. M. (1985) · Theoretical Computer Science · doi:10.1016/0304-3975(85)90073-8 · Cited by 35
Adami, C. (1994) · Artificial Life · doi:10.1162/artl.1994.1.429 · Cited by 35
A completeness problem for pattern generation in tessellation automata
Yamada, H., & Amoroso, S. (1970) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(70)80005-8 · Cited by 25
Active Mutation in Self-Reproducing Networks of Machines and Tapes
Ikegami, T., & Hashimoto, T. (1995) · Artificial Life · doi:10.1162/artl.1995.2.3.305 · Cited by 24
Survey of research in the theory of homogeneous structures and their applications
Aladyev, V. (1974) · Mathematical Biosciences · doi:10.1016/0025-5564(74)90088-1 · Cited by 23
Completeness problem of one-dimensional binary scope-3 tessellation automata
Maruoka, A., & Kimura, M. (1974) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(74)80036-x · Cited by 10
Cited by
Cellular automata models of road traffic
Maerivoet, S., & De Moor, B. (2005) · Physics Reports · doi:10.1016/j.physrep.2005.08.005 · Cited by 602
(2002) · Springer eBooks · doi:10.1007/978-1-4471-0129-1 · Cited by 298
M ig C lim: Predicting plant distribution and dispersal in a changing climate
Engler, R., & Guisan, A. (2009) · Diversity and Distributions · doi:10.1111/j.1472-4642.2009.00566.x · Cited by 285
A novel image encryption algorithm using chaos and reversible cellular automata
Wang, X., & Luan, D. (2013) · Communications in Nonlinear Science and Numerical Simulation · doi:10.1016/j.cnsns.2013.04.008 · Cited by 216
Design of image cipher using life-like cellular automata and chaotic map
Ping, P., Wu, J., Mao, Y., Xu, F., & Fan, J. (2018) · Signal Processing · doi:10.1016/j.sigpro.2018.04.018 · Cited by 71
Metadata
- Authors
- Sarkar, P.
- Venue
- ACM Computing Surveys
- Published
- 2000-03
- Volume
- 32
- Issue
- 1
- Pages
- 80-107
- ISSN
- 0360-0300 (ISSN-L)
- 1557-7341
- OpenAlex
- W2014144020
- Cited by
- 384
- References
- 58
- FWCI
- 7.65
- Type
- journal article
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.