The DOI matches its Crossref record; 36 of the 36 references it cites were found in a registry or an index.
Theory of cellular automata: A survey
Open accessAbstract
This article surveys some theoretical aspects of cellular automata CA research. In particular, we discuss classical and new results on reversibility, conservation laws, limit sets, decidability questions, universality and topological dynamics of CA. The selection of topics is by no means comprehensive and reflects the research interests of the author. The main goal is to provide a tutorial of CA theory to researchers in other branches of natural computing, to give a compact collection of known results with references to their proofs, and to suggest some open problems.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
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
Logical Reversibility of Computation
Bennett, C. H. (1973) · IBM Journal of Research and Development · doi:10.1147/rd.176.0525 · Cited by 3,679
Statistical mechanics of cellular automata
Wolfram, S. (1983) · Reviews of Modern Physics · doi:10.1103/revmodphys.55.601 · Cited by 3,114
Lattice-gas automata for the Navier-Stokes equation
Frisch, U., Hasslacher, B., & Pomeau, Y. (1986) · Physical Review Letters · doi:10.1103/physrevlett.56.1505 · Cited by 2,788
An Introduction to Chaotic Dynamical Systems
Devaney, R. L., & Eckmann, J.-P. (1987) · Physics Today · doi:10.1063/1.2820117 · Cited by 2,344
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
Witten, T. A., & Sander, L. M. (1983) · Physical Review B · doi:10.1103/physrevb.27.5686 · Cited by 1,856
Theory and Applications of Cellular Automata
Wolfram, S. (1986) · Cited by 1,743
(1990) · Acta Applicandae Mathematicae · doi:10.1007/bf00049580 · Cited by 1,603
Cellular Automata Machines: A New Environment for Modeling
Toffoli, T., & Margolus, N. (1987) · The MIT Press eBooks · doi:10.7551/mitpress/1763.001.0001 · Cited by 1,425
Codd, E. F. (1968) · Cited by 1,366
Cellular Automata Modeling of Physical Systems
Chopard, B., & Droz, M. (1998) · Cambridge University Press eBooks · doi:10.1017/cbo9780511549755 · Cited by 1,043
Endomorphisms and automorphisms of the shift dynamical system
Hedlund, G. A. (1969) · Theory of Computing Systems · doi:10.1007/bf01691062 · Cited by 1,034
Cellular Automata Machines: A New Environment for Modeling
Toffoli, T., & Margolus, N. (1987) · Cited by 933
Cellular Automata Modeling of Physical Systems
(2011) · SpringerReference · doi:10.1007/springerreference_60229 · Cited by 870
Proving Theorems by Pattern Recognition - II
Wang, H. (1961) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1961.tb03975.x · Cited by 862
Undecidability and nonperiodicity for tilings of the plane
Robinson, R. M. (1971) · Inventiones mathematicae · doi:10.1007/bf01418780 · Cited by 697
Burks, A. W. (1970) · Medical Entomology and Zoology · Cited by 663
Simulating physics with cellular automata
Vichniac, G. Y. (1984) · Physica D: Nonlinear Phenomena · doi:10.1016/0167-2789(84)90253-7 · Cited by 500
Molecular dynamics of a classical lattice gas: Transport properties and time correlation functions
Hardy, J., de Pazzis, O., & Pomeau, Y. (1976) · Physical Review A · doi:10.1103/physreva.13.1949 · Cited by 444
Physics-like models of computation
Margolus, N. (1984) · Physica D: Nonlinear Phenomena · doi:10.1016/0167-2789(84)90252-5 · Cited by 407
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
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
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
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
Undecidability of CA Classification Schemes
Čulík, K., & Yü, S. (1988) · Complex Systems · Cited by 129
Computation Universality of One-Dimensional Reversible (Injective) Cellular Automata
Morita, K., & Harao, M. (1989) · Institutional Repositories DataBase (IRDB) · Cited by 117
A Simple Universal Cellular Automaton and its One-Way and Totalistic Version.
Albert, J., & Čulík, K. (1987) · Complex Systems · Cited by 108
Representation of Reversible Cellular Automata with Block Permutations
Kari, J. (1996) · Theory of Computing Systems · doi:10.1007/bf01201813 · Cited by 91
Self-citationAdditive conserved quantities in discrete-time lattice dynamical systems
Hattori, T., & Takesue, S. (1991) · Physica D Nonlinear Phenomena · doi:10.1016/0167-2789(91)90150-8 · Cited by 85
Cellular Automata and Complex Systems
Chacc, E. G., & Martı́nez, S. (1999) · Nonlinear phenomena and complex systems · doi:10.1007/978-94-015-9223-9 · Cited by 59
On the Circuit Depth of Structurally Reversible Cellular Automata
Kari, J. (1999) · Fundamenta Informaticae · doi:10.3233/fi-1999-381208 · Cited by 30
Self-citationA Tight Linear Bound on the Neighborhood of Inverse Cellular Automata
Czeizler, E., & Kari, J. (2005) · Lecture notes in computer science · doi:10.1007/11523468_34 · Cited by 23
Self-citation
Cited by
Tumor-Cut: Segmentation of Brain Tumors on Contrast Enhanced MR Images for Radiosurgery Applications
Hamamci, A., Kucuk, N., Karaman, K., Engin, K., & Unal, G. (2012) · IEEE Transactions on Medical Imaging · doi:10.1109/tmi.2011.2181857 · Cited by 286
Enayatifar, R., Sadaei, H. J., Abdullah, A. H., Lee, M., & Isnin, I. F. (2015) · Optics and Lasers in Engineering · doi:10.1016/j.optlaseng.2015.03.007 · Cited by 144
Albantakis, L., & Tononi, G. (2015) · Entropy · doi:10.3390/e17085472 · Cited by 58
Dirac Cellular Automaton from Split-step Quantum Walk
Mallick, A., & Chandrashekar, C. M. (2016) · Scientific Reports · doi:10.1038/srep25779 · Cited by 45
“The state update rule acts synchronously at every position called the lattice point where the unit cells of the lattice are all identical with the underlying graph being regular [54].”
Background
Metadata
- Authors
- Kari, J.
- Venue
- Theoretical Computer Science
- Publisher
- Elsevier BV
- Published
- 2005-04
- Volume
- 334
- Issue
- 1-3
- Pages
- 3-33
- ISSN
- 0304-3975 (ISSN-L)
- OpenAlex
- W2022060148
- Cited by
- 625
- References
- 36
- FWCI
- 14.75
- 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.