Theory of cellular automata: a survey

DOI10.1016/j.tcs.2004.11.021zbMath1080.68070OpenAlexW2022060148WikidataQ62045962 ScholiaQ62045962MaRDI QIDQ1779295

Jarkko Kari

Publication date: 1 June 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.11.021

zbMATH Keywords

surveyconservation lawscellular automatatopological dynamicsuniversalitylimit setsreversible computationtutorial

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80) Dynamical aspects of cellular automata (37B15) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Research exposition (monographs, survey articles) pertaining to dynamical systems and ergodic theory (37-02)

Related Items (only showing first 100 items - show all)

Explicit routing schemes for implementation of cellular automata on processor arrays ⋮ A dynamical study of a cellular automata model of the spread of HIV in a lymph node ⋮ Ergodicity of some classes of cellular automata subject to noise ⋮ On the spatial dynamics and oscillatory behavior of a predator-prey model based on cellular automata and local particle swarm optimization ⋮ Real-time reversible iterative arrays ⋮ A Characterization of Cellular Automata Generated by Idempotents on the Full Shift ⋮ An “almost dual” to Gottschalk’s Conjecture ⋮ On Finite Monoids of Cellular Automata ⋮ Sum of Exit Times in Series of Metastable States in Probabilistic Cellular Automata ⋮ Partial Reversibility of One-Dimensional Cellular Automata ⋮ Effect of self-interaction on the phase diagram of a Gibbs-like measure derived by a reversible probabilistic cellular automata ⋮ A study on delay-sensitive cellular automata ⋮ Overview: PCA Models and Issues ⋮ Basic Ideas to Approach Metastability in Probabilistic Cellular Automata ⋮ Statistical Equilibrium in Deterministic Cellular Automata ⋮ Ranks of finite semigroups of one-dimensional cellular automata ⋮ Counter machines and distributed automata -- a story about exchanging space and time ⋮ Cellular non-deterministic automata and partial differential equations ⋮ Ternary reversible number-conserving cellular automata are trivial ⋮ A search for good pseudo-random number generators: survey and empirical studies ⋮ An order-preserving property of additive invariants for Takesue-type reversible cellular automata ⋮ Reversibility problem of multidimensional finite cellular automata ⋮ Multidimensional cellular automata: closing property, quasi-expansivity, and (un)decidability issues ⋮ Progress, gaps and obstacles in the classification of cellular automata ⋮ Statistical mechanics of surjective cellular automata ⋮ Four states are enough! ⋮ Abstract geometrical computation. IV: Small Turing universal signal machines ⋮ A new network approach to Bayesian inference in partial differential equations ⋮ The Most General Conservation Law for a Cellular Automaton ⋮ Nivat's conjecture and pattern complexity in algebraic subshifts ⋮ Fundamentals of reversible flowchart languages ⋮ Rapid left expansivity, a commonality between Wolfram's rule 30 and powers of \(p/q\) ⋮ An automaton group with undecidable order and Engel problems ⋮ Invertibility and nonsingularity of Boolean control networks ⋮ Universal pattern generation by cellular automata ⋮ Semipredictable dynamical systems ⋮ Limit set problem of multi-agent systems with finite states: an eigenvalue-based approach ⋮ Maximum number of periodic orbits in parallel dynamical systems ⋮ Varieties of agents in agent-based computational economics: a historical and an interdisciplinary perspective ⋮ Topological dynamics of nondeterministic cellular automata ⋮ Elementary, finite and linear vN-regular cellular automata ⋮ Maximum sensitivity to update schedules of elementary cellular automata over infinite configurations ⋮ Shift-equivalence of \(k\)-ary, one-dimensional cellular automata rules ⋮ The Thue-Morse-Pascal double sequence and similar structures ⋮ Groups, graphs, languages, automata, games and second-order monadic logic ⋮ Finite entropy for multidimensional cellular automata ⋮ Mathematical models for tumours with cancer stem cells ⋮ A perfect solution to the parity problem with elementary cellular automaton 150 under asynchronous update ⋮ Polyominoes simulating arbitrary-neighborhood zippers and tilings ⋮ Reversible computing and cellular automata -- a survey ⋮ Extraction of characteristic features of images with the help of the Radon transform and its hardware implementation in terms of cellular automata ⋮ Simulation of a vibrant membrane using a 2-dimensional cellular automaton ⋮ Evolution of cooperation with Moore neighborhood and self-playing rule ⋮ Cellular Automata-Based Structures to Compute the Solutions of Linear Difference Equations ⋮ Around probabilistic cellular automata ⋮ Markovianity of the invariant distribution of probabilistic cellular automata on the line ⋮ Snakes and Cellular Automata: Reductions and Inseparability Results ⋮ Fast reversible language recognition using cellular automata ⋮ Failure risk propagation and protection schemes in coupled systems ⋮ A generalized neighborhood for cellular automata ⋮ Reversibility of general 1D linear cellular automata over the binary field \(\mathbb{Z}_2\) under null boundary conditions ⋮ How and how much to invest for fighting cheaters: from an ODE to a cellular automata model ⋮ Computational complexity of finite asynchronous cellular automata ⋮ Characterisation of the elementary cellular automata with neighbourhood priority based deterministic updates ⋮ RECURRENT DOUBLE SEQUENCES THAT CAN BE PRODUCED BY CONTEXT-FREE SUBSTITUTIONS ⋮ Dynamical properties of a cellular automaton on a countable group ⋮ Picture deformation ⋮ Supercritical probabilistic cellular automata: how effective is the synchronous updating? ⋮ Expansive automata networks ⋮ On the hierarchy of conservation laws in a cellular automaton ⋮ Modeling and analyzing social network dynamics using stochastic discrete graphical dynamical systems ⋮ Graph transformation through graph surfing in reaction systems ⋮ Permutive one-way cellular automata and the finiteness problem for automaton groups ⋮ On the periods of parallel dynamical systems ⋮ Linear solutions for cryptographic nonlinear sequence generators ⋮ Periodicity and Immortality in Reversible Computing ⋮ A simple linearization of the self-shrinking generator by means of cellular automata ⋮ Leader election on two-dimensional periodic cellular automata ⋮ EMERGENT 1D ISING BEHAVIOR IN AN ELEMENTARY CELLULAR AUTOMATON MODEL ⋮ Synthesis of cryptographic interleaved sequences by means of linear cellular automata ⋮ Mutually orthogonal Latin squares based on cellular automata ⋮ On the topological directional entropy ⋮ When-and how-can a cellular automaton be rewritten as a lattice gas? ⋮ Embedding dynamical networks into distributed models ⋮ The 4-way deterministic tiling problem is undecidable ⋮ On the dynamics and recursive properties of multidimensional symbolic systems ⋮ LUNAR: cellular automata for drifting data streams ⋮ Self-similar carpets over finite fields ⋮ Autonomous population regulation using a multi-agent system in a prey-predator model that integrates cellular automata and the African buffalo optimization metaheuristic ⋮ CURIE: a cellular automaton for concept drift detection ⋮ Some applications of propositional logic to cellular automata ⋮ An asynchronous solution to the synchronisation problem for binary one-dimensional cellular automata ⋮ Solutions to all-colors problem on graph cellular automata ⋮ From multiple to single updates per cell in elementary cellular automata with neighbourhood based priority ⋮ A spectral outlook on the elementary cellular automata with cyclic configurations and block-sequential asynchronous updates ⋮ Mutation systems ⋮ Parallel dynamical systems over graphs and related topics: a survey ⋮ Decidability and undecidability in cellular automata ⋮ Conserved quantities in discrete dynamics: what can be recovered from Noether's theorem, how, and why? ⋮ Geometric computations by broadcasting automata

Cites Work

• On real time one-way cellular array
• On real-time cellular automata and trellis automata
• Formal languages and global cellular automaton behavior
• Reversibility of 2D cellular automata is undecidable
• Invertible cellular automata: A review
• Linear cellular automata over \(Z_ m\)
• Reliable computation with cellular automata
• Dynamical characteristics of linear cellular automata
• A six-state minimal time solution to the Firing squad synchronization problem
• Relating the power of cellular arrays to their closure properties
• An aperiodic set of 13 Wang tiles
• A small aperiodic set of Wang tiles
• Additive conserved quantities in discrete-time lattice dynamical systems
• Computation and construction universality of reversible cellular automata
• Decidability for some problems of linear cellular automata over finite commutative rings
• Invertible linear cellular automata over \(\mathbb{Z}_m\): Algorithmic and dynamical aspects
• Lyapunov exponent versus expansivity and sensitivity in cellular automata
• Expansiveness, entropy and polynomial growth for groups acting on subshifts by automorphisms
• Reversibility and surjectivity problems of cellular automata
• Inversion of 2D cellular automata: Some complexity results
• Rice's theorem for the limit sets of cellular automata
• Dynamical properties of expansive one-sided cellular automata
• Ergodicity, transitivity, and regularity for linear cellular automata over \(\mathbb{Z}_m\)
• A complete and efficiently computable topological classification of D-dimensional linear cellular automata over \(Z_{m}\)
• Undecidability and nonperiodicity for tilings of the plane
• Tesselations with local transformations
• Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures
• Real-time language recognition by one-dimensional cellular automata
• On the Limit Sets of Cellular Automata
• Statistical mechanics of cellular automata
• One-way bounded cellular automata
• The Nilpotency Problem of One-Dimensional Cellular Automata
• The topological entropy of cellular automata is uncomputable
• Languages, equicontinuity and attractors in cellular automata
• Representation of reversible cellular automata with block permutations
• Cellular Automata Modeling of Physical Systems
• Shorter Note: The Converse of Moore's Garden-of-Eden Theorem
• Endomorphisms and automorphisms of the shift dynamical system
• The undecidability of the domino problem
• Logical Reversibility of Computation
• Automata, Languages and Programming
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Theory of cellular automata: a survey