A survey of cellular automata: types, dynamics, non-uniformity and applications
From MaRDI portal
Publication:6151179
DOI10.1007/S11047-018-9696-8zbMATH Open1530.68158arXiv1607.02291OpenAlexW2963131442MaRDI QIDQ6151179FDOQ6151179
Authors: Kamalika Bhattacharjee, Nazma Naskar, Souvik Roy, Sukanta Das 
Publication date: 9 February 2024
Published in: Natural Computing (Search for Journal in Brave)
Abstract: Cellular automata (CAs) are dynamical systems which exhibit complex global behavior from simple local interaction and computation. Since the inception of cellular automaton (CA) by von Neumann in 1950s, it has attracted the attention of several researchers over various backgrounds and fields for modelling different physical, natural as well as real-life phenomena. Classically, CAs are uniform. However, non-uniformity has also been introduced in update pattern, lattice structure, neighborhood dependency and local rule. In this survey, we tour to the various types of CAs introduced till date, the different characterization tools, the global behaviors of CAs, like universality, reversibility, dynamics etc. Special attention is given to non-uniformity in CAs and especially to non-uniform elementary CAs, which have been very useful in solving several real-life problems.
Full work available at URL: https://arxiv.org/abs/1607.02291
Recommendations
Cites Work
- Collective dynamics of `small-world' networks
- Conservative logic
- Theory of cellular automata: a survey
- Probing robustness of cellular automata through variations of asynchronous updating
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Universality in elementary cellular automata
- Endomorphisms and automorphisms of the shift dynamical system
- Languages, equicontinuity and attractors in cellular automata
- A logical calculus of the ideas immanent in nervous activity
- Four states are enough!
- Reversible computing and cellular automata -- a survey
- On the directional dynamics of additive cellular automata
- (A-)synchronous (non)-deterministic cell spaces simulating each other
- Reversibility and surjectivity problems of cellular automata
- Solution of some conjectures about topological properties of linear cellular automata
- Fully asynchronous behavior of double-quiescent elementary cellular automata
- Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures
- Asynchronous cellular automata and dynamical properties
- \(m\)-asynchronous cellular automata: from fairness to quasi-fairness
- Solving the parity problem in one-dimensional cellular automata
- Non-uniform Cellular Automata
- Statistical mechanics of cellular automata
- Title not available (Why is that?)
- Multidimensional cellular automata: closing property, quasi-expansivity, and (un)decidability issues
- Local rule distributions, language complexity and non-uniform cellular automata
- The Nilpotency Problem of One-Dimensional Cellular Automata
- Title not available (Why is that?)
- Probabilistic cellular automata with conserved quantities
- Computing issues of asynchronous CA
- Periodic orbits and dynamical complexity in cellular automata
- Non-uniform cellular automata: classes, dynamics, and decidability
- Conservation of some dynamical properties for operations on cellular automata
- Title not available (Why is that?)
- On reversibility in cellular automata
- Dynamical properties of expansive one-sided cellular automata
- Transitive Cellular Automata are Sensitive
- Cellular Automata Modeling of Physical Systems
- Title not available (Why is that?)
- Investigating topological chaos by elementary cellular automata dynamics
- Tesselations with local transformations
- CELLULAR AUTOMATON MODELS OF TUMOR DEVELOPMENT: A CRITICAL REVIEW
- Algebraic Theory of Automata Networks
- Simple Computation-Universal Cellular Spaces
- Title not available (Why is that?)
- Title not available (Why is that?)
- Amenable groups and cellular automata
- Garden of Eden Configurations for Cellular Automata on Cayley Graphs of Groups
- Title not available (Why is that?)
- Shorter Note: The Converse of Moore's Garden-of-Eden Theorem
- Design of CAECC - cellular automata based error correcting code
- CAR30: a new scalable stream cipher with rule 30
- Lyapunov exponent versus expansivity and sensitivity in cellular automata
- Lyapunov exponents for one-dimensional cellular automata
- Determining a regular language by glider-based structures calles phases \(f_i\)\_1 in Rule 110
- Computation theoretic aspects of cellular automata
- Stochastic cellular automata solutions to the density classification problem. When randomness helps computing
- Title not available (Why is that?)
- Algebraic properties of cellular automata
- Title not available (Why is that?)
- A universal cellular automaton in quasi-linear time and its S-m-n form
- Number-conserving cellular automata I: Decidability.
- Title not available (Why is that?)
- Title not available (Why is that?)
- One-way bounded cellular automata
- Title not available (Why is that?)
- Reversibility of 2D cellular automata is undecidable
- Random sequence generation by cellular automata
- Two-dimensional cellular automata
- Outer-totalistic cellular automata on graphs
- Asynchronous mappings and asynchronous cellular automata
- Title not available (Why is that?)
- Developments in Language Theory
- Invertible cellular automata: A review
- Synchronous to asynchronous transformation of polyautomata
- Additive conserved quantities in discrete-time lattice dynamical systems
- Universality and decidability of number-conserving cellular automata
- On invertible three neighborhood null-boundary uniform cellular automata
- Three research directions in non-uniform cellular automata
- Realization problems for nonuniform cellular automata
- The firing squad synchronization problem on CA with multiple updating cycles
- Linear cellular automata over \(Z_ m\)
- Title not available (Why is that?)
- Computation and construction universality of reversible cellular automata
- A computation-universal two-dimensional 8-state triangular reversible cellular automaton
- Guided tour of asynchronous cellular automata
- Two-dimensional cellular automata and their neighborhoods
- On the dynamical behavior of chaotic cellular automata
- Reversibility in asynchronous cellular automata
- Title not available (Why is that?)
- The inverse behavior of a reversible one-dimensional cellular automaton obtained by a single Welch diagram
- Reversibility of linear cellular automata
- Reversibility of 1D cellular automata with periodic boundary over finite fields \({\mathbb{Z}}_{p}\)
- Multidimensional \(\sigma\)-automata, \(\pi\)-polynomials and generalised S-matrices
- Computation of explicit preimages in one-dimensional cellular automata applying the De Bruijn diagram
- Cellular automaton rules conserving the number of active sites
- Title not available (Why is that?)
- Conservation laws in cellular automata
- HOW TO SIMULATE TURING MACHINES BY INVERTIBLE ONE-DIMENSIONAL CELLULAR AUTOMATA
- Communication complexity in number-conserving and monotone cellular automata
- Generation of Primes by a One-Dimensional Real-Time Iterative Array
- Cellular automata complexity trade-offs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Leader election in d-dimensional CA in time diam log(diam)
- A perimeter--time CA for the queen bee problem
- NP problems are tractable in the space of cellular automata in the hyperbolic plane
- Title not available (Why is that?)
- Transition phenomena in cellular automata rule space
- Number conserving cellular automata. II: Dynamics.
- Automorphisms of \(\mathbb Z^ d\)-subshifts of finite type
- Characterisation of a particular hybrid transformation of two-dimensional cellular automata
- Parameter characterization of two-dimensional cellular automata rule space
- PERFORMANCE AND ROBUSTNESS OF CELLULAR AUTOMATA COMPUTATION ON IRREGULAR NETWORKS
- Reversible simulation of one-dimensional irreversible cellular automata
- Title not available (Why is that?)
- Evolution and dynamics of small-world cellular automata
- Elementary cellular automata with minimal memory and random number generation
- Characterization of Reachable/Nonreachable Cellular Automata States
- The Garden-of-Eden Theorem for Finite Configurations
- Certain relations between properties of maps of tessellation automata
- Injectivity and surjectivity of parallel maps for cellular automata
- Title not available (Why is that?)
- Condition for injectivity of global maps for tessellation automata
- Simple self-reproducing universal automata
- Title not available (Why is that?)
- Universality of Reversible Hexagonal Cellular Automata
- Cryptographic properties of bipermutive cellular automata rules
- Advances on random sequence generation by uniform cellular automata
- Computation of shortest path in cellular automata
- Asynchronous automata versus asynchronous cellular automata
- Petri net implementations by a universal cell space
- On the generation of high-quality random numbers by two-dimensional cellular automata
- Title not available (Why is that?)
- Group Properties of Cellular Automata and VLSI Applications
- Title not available (Why is that?)
- Asynchronous cellular automata for pomsets
- Exploring cycle structures of additive cellular automata
- Title not available (Why is that?)
- Fault tolerant cellular spaces
- On the interconnection structure of cellular networks
- An efficient solution of the firing mob problem
- On characterization of cellular automata with matrix algebra
- Title not available (Why is that?)
- Discrete parabolas and circles on 2D cellular automata
- Vector space theoretic analysis of additive cellular automata and its application for pseudoexhaustive test pattern generation
- Analysis of periodic and intermediate boundary 90/150 cellular automata
- Cryptographically suitable maximum length cellular automata
- Theory and application of nongroup cellular automata for synthesis of easily testable finite state machines
- Graph-theoretical characterization of invertible cellular automata
- Structure and reversibility of 2D hexagonal cellular automata
- Reversibility algorithms for 3-state hexagonal cellular automata with periodic boundaries
- Title not available (Why is that?)
- The 3-dimensional cellular automata for HIV infection
- Title not available (Why is that?)
- Comparison between simultaneous and sequential updating in \(2^{n+1}-1\) cellular automata
- Simple 8-state minimal time solution to the firing squad synchronization problem
- Number-conserving reversible cellular automata and their computation-universality
- Title not available (Why is that?)
- Reversibility of elementary cellular automata under fully asynchronous update
- Generalized Automata Networks
- On synthesis of non-uniform cellular automata having only point attractors
- Universality of 8-State Reversible and Conservative Triangular Partitioned Cellular Automata
- Configuration symmetry and performance upper bound of one-dimensional cellular automata for the leader election problem
- Distributed mutual exclusion problem in cellular automata
- Number conservation property of elementary cellular automata under asynchronous update
- Self-replicating patterns in 2D linear cellular automata
- Block cipher based on reversible cellular automata
- Evolving two-dimensional cellular automata to perform density classification: A report on work in progress
- Title not available (Why is that?)
- About the Garden of Eden theorems for cellular automata in the hyperbolic plane
- Characterization of single cycle CA and its application in pattern classification
- Characterization of 1-d periodic boundary reversible CA
- Modified traffic cellular automaton for the density classification task
- Conceptual connections around density determination in cellular automata
- Title not available (Why is that?)
- Remarks on applications of de Bruijn diagrams and their fragments
- Pair diagram and cyclic properties characterizing the inverse of reversible automata
- Title not available (Why is that?)
- Cellular Automata Based Encoding Technique for Wavelet Transformed Data Targeting Still Image Compression
- An Analytical Formulation for Cellular Automata (CA) Based Solution of Density Classification Task (DCT)
- Characterization of Non-reachable States in Irreversible CA State Space
- Title not available (Why is that?)
- Title not available (Why is that?)
- Asynchrony immune cellular automata
- Theory and application of equal length cycle cellular automata (ELCCA) for enzyme classification
- Linear time algorithm for identifying the invertibility of null-boundary three neighborhood cellular automata
- Cellular Automata Based Encompression Technology for Voice Data
Cited In (9)
- Simulation of non-uniform cellular automata by classical cellular automata and its application in embedded systems
- Generation of pseudo-isomorphic cellular automata
- Lyapunov Profiles of Three-State Totalistic Cellular Automata
- Wildfire Simulation Model Based on Cellular Automata and Stochastic Rules
- A comprehensive taxonomy of cellular automata
- Number conservation via particle flow in one-dimensional cellular automata
- Associating parallel automata network dynamics and strictly one-way cellular automata
- Pattern classification with temporally stochastic cellular automata
- Lyapunov exponents of multi-state cellular automata
This page was built for publication: A survey of cellular automata: types, dynamics, non-uniformity and applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6151179)
