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 (74)

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

• 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
• 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: Invertible cellular automata: A review