Computation theoretic aspects of cellular automata

https://doi.org/10.1016/0167-2789(90)90194-TGet rights and content

Abstract

Cellular automata may be viewed as computational models of complex systems. They also can be seen as continuous functions on a particular family of compact metric spaces. This paper surveys results largely motivated by an attempt to answer questions posed by the latter approach by means of techniques from the former.

References (72)

  • M. Hurley, Attractors in cellular automata, Ergodic Theor. Dynam. Systems, to...
  • M. Hurley, Ergodic aspects of cellular automata, to...
  • T. Toffoli

    Computation and construction universality of reversible automata

    J. Computer System Sci.

    (1977)
  • K. Culik

    On invertible cellular automata

    Complex Systems

    (1987)
  • S. Dube

    An investigation of cellular automata

  • J. von Neumann
  • K. Culik et al.

    Undecidability of CA classification schemes

    Complex Systems

    (1988)
  • L.P. Hurd

    Formal language characterizations of cellular automaton limit sets

    Complex Systems

    (1987)
  • S. Ginsburg

    Algebraic and Automata-Theoretic Properties of Formal Languages

    (1975)
  • J.L. Kelley

    General Topology

    (1955)
  • G.A. Hedlund

    Transformations commuting with the shift

    Endomorphisms and automorphisms of the shift dynamical system

    Math. Syst. Theor.

    (1969)
  • M.A. Arbib

    Simple self-reproducing universal automata

    Information Control

    (1966)
  • M. Minsky

    Computation: Finite and Infinite Machines

    (1967)
  • L. Priese

    Towards a precise characterization of the complexity of universal and nonuniversal Turing Machines

    SIAM J. Comput.

    (1979)
  • A.R. Smith

    Simple computation-universal cellular spaces

    J. ACM

    (1971)
  • C.R. Dyer

    One way bounded cellular automata

    Information Control

    (1980)
  • H. Umeo et al.

    Deterministic one-way simulation of two-way real-time cellular automata and its related problems

    Information Processing Lett.

    (1982)
  • D. Gordon, On the computational power of totalistic cellular automata,...
  • K. Culik et al.

    On totalistic systolic networks

    Information Processing Lett.

    (1987/1988)
  • E.R. Berlekamp et al.M. Gardner

    Wheels, Life and Other Mathematical Amusements

    (1983)
  • S. Wolfram

    Twenty problems in the theory of cellular automata

    Physica Scripta

    (1985)
  • K. Sutner

    The computational complexity of cellular automata

  • H.A. Gutowitz

    A hierarchical classification of cellular automata

    Physica D

    (1990)
  • H.A. Gutowitz et al.

    Local structure theory of cellular automata

    Physica D

    (1987)
  • R. Gilman

    Periodic behavior of linear automata

  • K. Culik et al.

    On the limit sets of cellular automata

    SIAM J. Computing

    (1989)
  • Cited by (89)

    • A Coupling Model of Net Primary Productivity Pattern Simulation and Prediction

      2021, Wuhan Daxue Xuebao (Xinxi Kexue Ban)/Geomatics and Information Science of Wuhan University
    View all citing articles on Scopus
    1

    On leave from Kent State University, Kent, OH 44242, USA.

    View full text