Invertible cellular automata: A review

DOI10.1016/0167-2789(90)90185-RzbMath0729.68066OpenAlexW2039585018WikidataQ30054102 ScholiaQ30054102MaRDI QIDQ807058

Tommaso Toffoli, Norman H. Margolus

Publication date: 1990

Published in: Physica D (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-2789(90)90185-r

zbMATH Keywords

computer sciencereviewmathematical physicsinvertible cellular automata

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80)

Related Items

Invertible shift-invariant transformations on binary arrays, A new symmetrical cryptosystem based cellular automata and chaotic map function, Efficient exhaustive listings of reversible one dimensional cellular automata, On the size of the inverse neighborhoods for one-dimensional reversible cellular automata, The complexity of reversible cellular automata, How to turn a second-order cellular automaton into a lattice gas: a new inversion scheme, Intrinsic universality of a 1-dimensional reversible Cellular Automaton, Predecessors of cellular automata states. II: Pre-images of finite sequences, The surjectivity problem for 2D cellular automata, Universality of a reversible two-counter machine, Self-reproduction in a reversible cellular space, Inverse rules of ECA with rule number 150, What Automata Can Provide a Medium for Life?, Partial Reversibility of One-Dimensional Cellular Automata, Nonequilibrium Physics Aspects of Probabilistic Cellular Automata, Additive cellular automata and global injectivity, A reversible steganography scheme of secret image sharing based on cellular automata and least significant bits construction, Running programs backwards: The logical inversion of imperative computation, Reversible cellular automaton able to simulate any other reversible one using partitioning automata, Statistical mechanics of surjective cellular automata, Reversible spiking neural P systems, Communication complexity meets cellular automata: necessary conditions for intrinsic universality, A survey of cellular automata: types, dynamics, non-uniformity and applications, Simulation and Intrinsic Universality Among Reversible Cellular Automata, the Partition Cellular Automata Leverage, Waiting for the rapture: what can we do with computers to (hopefully) witness the emergence of life?, Representation of reversible cellular automata with block permutations, Reversible computing from a programming language perspective, On time-symmetry in cellular automata, Description of systematicity intrinsic to the dynamics of complex-system models., Reversibility of computations in graph-walking automata, Reversible computing and cellular automata -- a survey, On the absence of homogeneous scalar unitary cellular automata., Structure of the invertible CA transformations group, Distributed Multi-authority Attribute-Based Encryption Using Cellular Automata, A two-layer representation of four-state reversible number-conserving 2D cellular automata, Hybrid one-dimensional reversible cellular automata are regular, A Random NP-complete problem for inversion of 2D cellular automata, The reachability problem for finite cellular automata, Fast reversible language recognition using cellular automata, Nondeterministic cellular automata, Continuity of information transport in surjective cellular automata, A multisecret sharing scheme for color images based on cellular automata, Computational universes, Number-Conserving Reversible Cellular Automata and Their Computation-Universality, Block cipher based on reversible cellular automata, A secure scheme to share secret color images, Theory of cellular automata: a survey, A lattice Boltzmann equation for diffusion, A verifiable multi-secret sharing scheme based on cellular automata, Time-reversal symmetry in dynamical systems: a survey, Universality of Reversible Hexagonal Cellular Automata, Secret image sharing based on cellular automata and steganography, When-and how-can a cellular automaton be rewritten as a lattice gas?, Characterization of 1-d Periodic Boundary Reversible CA, Design of fast one-pass authenticated and randomized encryption schema using reversible cellular automata, Invertible linear cellular automata over \(\mathbb{Z}_m\): Algorithmic and dynamical aspects, Cellular Automata with Random Memory and Its Implementations, REVERSIBILITY OF A SYMMETRIC LINEAR CELLULAR AUTOMATA, CONSTRUCTION OF REVERSIBLE LATTICE MOLECULAR AUTOMATA, Autonomous population regulation using a multi-agent system in a prey-predator model that integrates cellular automata and the African buffalo optimization metaheuristic, ON THE REVERSIBILITY OF 150 WOLFRAM CELLULAR AUTOMATA, From quantum cellular automata to quantum lattice gases, Reversibility of number-conserving 1D cellular automata: unlocking insights into the dynamics for larger state sets, On the induction operation for shift subspaces and cellular automata as presentations of dynamical systems, Nonconstructible blocks in 1D cellular automata: minimal generators and natural systems, Graph-theoretical characterization of invertible cellular automata, Investigation on the three-dimensional multiphase conjugate conduction problem inside porous wick with the lattice Boltzmann method, Parallel dynamical systems over graphs and related topics: a survey, Reversible cellular automata with memory: two-dimensional patterns from a single site seed, CELLULAR AUTOMATA OVER SEMI-DIRECT PRODUCT GROUPS: REDUCTION AND INVERTIBILITY RESULTS, Analysis of quantum particle automata for solving the density classification problem, Computation in reversible cellular automata, Transformations of one-dimensional cellular automaton rules by translation-invariant local surjective mappings, Randomness on full shift spaces

Cites Work

• 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
• Two-dimensional cellular automata
• A hierarchical classification of cellular automata
• Reversibility of 2D cellular automata is undecidable
• Representation of geometrical and topological quantities in cellular automata
• Reversible parallel computation: An evolving space-model
• Relaxation properties of elementary reversible cellular automata
• Computation theory of cellular automata
• Cellular automaton fluids. I: Basic theory
• Local structure theory for cellular automata
• Strong surjectivity is equivalent to C-injectivity
• Conservative logic
• State-transition structures in physics and in computation
• Quantum mechanical Hamiltonian models of discrete processes that erase their own histories: Application to Turing machines
• Some clarifications of the concept of a Garden-of-Eden configuration
• Computation and construction universality of reversible cellular automata
• Certain relations between properties of maps of tessellation automata
• Injectivity and surjectivity of parallel maps for cellular automata
• Reversibility and surjectivity problems of cellular automata
• Tesselations with local transformations
• Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures
• Information Theory and Statistical Mechanics
• Invariant in cellular automata
• Statistical mechanics of cellular automata
• Bicontinuous extensions of invertible combinatorial functions
• Condition for injectivity of global maps for tessellation automata
• Inverse and Injectivity of Parallel Relations Induced by Cellular Automata
• Local maps inducing surjective global maps of one-dimensional tessellation automata
• The automorphisms of the shift dynamical system are relatively sparse
• Logical Reversibility of Computation