Reversible computing and cellular automata -- a survey

DOI10.1016/j.tcs.2008.01.041zbMath1145.68036MaRDI QIDQ924686

Publication date: 19 May 2008

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

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

zbMATH Keywords

reversible Turing machine; reversible logic element; reversible cellular automata; computation-universality

Mathematics Subject Classification ID

68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)

68Q80: Cellular automata (computational aspects)

Related Items

The Degree of Irreversibility in Deterministic Finite Automata, ON 1D REVERSIBLE CELLULAR AUTOMATA WITH REFLECTIVE BOUNDARY OVER THE PRIME FIELD OF ORDER p, Simulation and Intrinsic Universality Among Reversible Cellular Automata, the Partition Cellular Automata Leverage, Cellular Automata: Descriptional Complexity and Decidability, Invertible Construction of Decimal-to-Binary Converter Using Reversible Elements, Logical Gates via Gliders Collisions, Clean Reversible Simulations of Ranking Binary Trees, The Computing Power of Determinism and Reversibility in Chemical Reaction Automata, On the Reversibility of ECAs with Fully Asynchronous Updating: The Recurrence Point of View, Queue Automata: Foundations and Developments, Dual P Systems, Real-Time Reversible One-Way Cellular Automata, Reversibility in the higher-order \(\pi\)-calculus, On reversible Turing machines and their function universality, Fluctuation-driven computing on number-conserving cellular automata, Emergence of universal global behavior from reversible local transitions in asynchronous systems, Reversibility of linear cellular automata, Reversibility of 1D cellular automata with periodic boundary over finite fields \({\mathbb{Z}}_{p}\), Simulating reversible Turing machines and cyclic tag systems by one-dimensional reversible cellular automata, Design of 1-tape 2-symbol reversible Turing machines based on reversible logic elements, Fundamentals of reversible flowchart languages, Reversing computation in membrane systems, Characterization of random fluctuation-based computation in cellular automata, Designing nanoscale counter using reversible gate based on quantum-dot cellular automata, The complexity of translationally invariant spin chains with low local dimension, Reversibility of general 1D linear cellular automata over the binary field \(\mathbb{Z}_2\) under null boundary conditions, Reversible pushdown automata, A class of recursive permutations which is primitive recursive complete, A closed formula for the inverse of a reversible cellular automaton with \((2 R + 1)\)-cyclic rule, Binary-decision-diagram-based decomposition of Boolean functions into reversible logic elements, One-way reversible multi-head finite automata, General design of reversible sequential machines based on reversible logic elements, Hierarchy and Expansiveness in 2D Subshifts of Finite Type, The Degree of Irreversibility in Deterministic Finite Automata, Computation in reversible cellular automata, Aspects of Reversibility for Classical Automata, How Can We Construct Reversible Machines Out of Reversible Logic Element with Memory?, Reversible Limited Automata, Reversible and Irreversible Computations of Deterministic Finite-State Devices, When input-driven pushdown automata meet reversiblity, CELLULAR AUTOMATON SUPERCOLLIDERS, One-Way Reversible Multi-head Finite Automata, Garbageless Reversible Implementation of Integer Linear Transformations

Cites Work