Logical Reversibility of Computation
From MaRDI portal
Publication:5684240
DOI10.1147/rd.176.0525zbMath0267.68024OpenAlexW2105259569WikidataQ54087185 ScholiaQ54087185MaRDI QIDQ5684240
Publication date: 1973
Published in: IBM Journal of Research and Development (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/4c7671550671deba9ec318d867522897f20e19ba
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) General topics in the theory of software (68N01)
Related Items
The stochastic thermodynamics of computation, Ternary logic design in topological quantum computing, Algorithmic arguments in physics of computation, A theory of Automated Market Makers in DeFi, Reversible Binary Coded Decimal Adders using Toffoli Gates, Undecidability of the Spectral Gap, A novel design of reversible quantum multiplier based on multiple-control Toffoli synthesis, Looking at Euler flows through a contact mirror: universality and undecidability, Reverse bisimilarity vs. forward bisimilarity, The Entropy and Reversibility of Cellular Automata on Cayley Tree, Descriptive Complexity of Reversible Languages Having Finitely Many Reduced Automata, Weakly and Strongly Irreversible Regular Languages, Bridging Causal Reversibility and Time Reversibility: A Stochastic Process Algebraic Approach, Reversing Unbounded Petri Nets, Energy complexity of computation, Towards a taxonomy for reversible computation approaches, Optimization of reversible control flow graphs, Saving memory space in deep neural networks by recomputing: a survey, Reversible causal graph dynamics: invertibility, block representation, vertex-preservation, Abelian Invertible Automata, Simulation and Intrinsic Universality Among Reversible Cellular Automata, the Partition Cellular Automata Leverage, Logical Gates via Gliders Collisions, Clean Reversible Simulations of Ranking Binary Trees, The Computing Power of Determinism and Reversibility in Chemical Reaction Automata, Queue Automata: Foundations and Developments, Small Universal Reversible Counter Machines, Reversible Top-Down Syntax Analysis, A universal quantum algorithm for weighted maximum cut and Ising problems, Full counting statistics approach to the quantum non-equilibrium Landauer bound, Quantum cost optimization algorithm for entanglement-based asymmetric quantum error correction, A universal non-conservative reversible elementary triangular partitioned cellular automaton that shows complex behavior, Energy complexity of regular languages, Reversible Two-Party Computations, Efficient designs of reversible BCD to EX-3 Converter with low quantum cost in nanoscale, Unnamed Item, Unnamed Item, Topological reversibility and causality in feed-forward networks, On the Fault Testing for Reversible Circuits, An Introduction to Quantum Computing, without the Physics, ANALYSIS OF QUANTUM FUNCTIONS, Total cost of operating an information engine, Imaginary groups: lazy monoids and reversible computation, Simplifying Chemical Reaction Network Implementations with Two-Stranded DNA Building Blocks, How Can We Construct Reversible Turing Machines in a Very Simple Reversible Cellular Automaton?, Reversibility of Executable Interval Temporal Logic Specifications, Unnamed Item, Reversible pushdown transducers, Analogies and differences between quantum and stochastic automata, Rush Hour is PSPACE-complete, or ``Why you should generously tip parking lot attendants, Computing with energy and chemical reactions, Concise Representations of Reversible Automata, AUTOMATIC AND POLYNOMIAL-TIME ALGEBRAIC STRUCTURES, Transducing reversibly with finite state machines, Transducing reversibly with finite state machines, CIRCUITS, THE GROUPS OF RICHARD THOMPSON, AND coNP-COMPLETENESS, Nullstellensatz size-degree trade-offs from reversible pebbling, A Universal Cellular Automaton Without Sensitive Subsystems, Real-Time Reversible One-Way Cellular Automata, Unnamed Item, The thermodynamic cost of quantum operations, Increasing complexity with quantum physics, Reversibility in the higher-order \(\pi\)-calculus, Computability and complexity of ray tracing, A reversible logical circuit synthesis algorithm based on decomposition of cycle representations of permutations, Milestone developments in quantum information and no-go theorems, Reversible top-down syntax analysis, Know the single-receptor sensing limit? Think again, Circuit complexity in interacting QFTs and RG flows, Unpredictability and the transmission of numbers, Quantum conservative many-valued computing, Optimization approaches for designing quantum reversible arithmetic logic unit, On reversible Turing machines and their function universality, The 50\% advanced information rule of the quantum algorithms, Information equation of state, User authentication based on quantum-dot cellular automata using reversible logic for secure nanocommunication, Real-time reversible iterative arrays, Modular adder designs using optimal reversible and fault tolerant gates in field-coupled QCA nanocomputing, Universality of a reversible two-counter machine, Self-reproduction in a reversible cellular space, On the computational power of dynamical systems and hybrid systems, Quantum mechanical algorithm for solving quadratic residue equation, Designing nanoscale counter using reversible gate based on quantum-dot cellular automata, A new reversible circuit synthesis algorithm based on cycle representations of permutations, Intractable problems in reversible cellular automata, ``Superconducting causal nets, Study of dynamical systems from the viewpoint of complexity and computational capabilities, On asymptotic gate complexity and depth of reversible circuits without additional memory, Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\), Automata theory based on quantum logic: Some characterizations, Physical versus computational complementarity. I, Running programs backwards: The logical inversion of imperative computation, Generation of invertible functions, On the physical implementation of logical transformations: generalized \(L\)-machines, A notion of information related to computation, Thermodynamic aspects of confidentiality, Open problems on information and feedback controlled systems, Quantum theory, namely the pure and reversible theory of information, Life as thermodynamic evidence of algorithmic structure in natural environments, Fundamentals of reversible flowchart languages, Linear programs in a simple reversible language., On the simulation of quantum Turing machines., Realization and synthesis of reversible functions, Can quantum entanglement detection schemes improve search?, Model-theoretic complexity of automatic structures, Reversible parallel computation: An evolving space-model, The (absence of a) relationship between thermodynamic and logical reversibility, The connection between logical and thermodynamic irreversibility, Uncertainty principle and minimal energy dissipation in the computer, Physics of selective systems: Computation and biology, A note on quantum related-key attacks, Novel parity-preserving designs of reversible 4-bit comparator, Aligning the representation and reality of computation with asynchronous logic automata, Reversible computing and cellular automata -- a survey, Conservative logic, Quantum mechanical Hamiltonian models of discrete processes that erase their own histories: Application to Turing machines, Exact Maxwell-Boltzmann, Bose-Einstein and Fermi-Dirac statistics, Holographic dark information energy, Exponentially more concise quantum recognition of non-RMM regular languages, Computation in finitary stochastic and quantum processes, Physical limits of inference, Implementing a one-bit reversible full adder using quantum-dot cellular automata, Novel designs of nanometric parity preserving reversible compressor, Inverse monoids associated with the complexity class NP, Reversible simulation of one-dimensional irreversible cellular automata, The mechanism of quantum computation, Reversible simulation of space-bounded computations, Universal computation and other capabilities of hybrid and continuous dynamical systems, Fast reversible language recognition using cellular automata, Minimal universal library for \(n\times n\) reversible circuits, Join inverse categories and reversible recursion, A DNA computing inspired computational model, The resource theory of informational nonequilibrium in thermodynamics, Novel designs of quantum reversible counters, Computation-universality of one-dimensional one-way reversible cellular automata, One-way permutations, computational asymmetry and distortion., Design of 1-tape 2-symbol reversible Turing machines based on reversible logic elements, Quantum circuit oracles for abstract machine computations, Simulating reversible Turing machines and cyclic tag systems by one-dimensional reversible cellular automata, The logic of optics and the optics of logic, Simulation of \(n\)-qubit quantum systems. I: Quantum registers and quantum gates, Maxwell's demon and the thermodynamics of computation, Notes on Landauer's principle, reversible computation, and Maxwell's demon, Computation and construction universality of reversible cellular automata, The complexity of small universal Turing machines: A survey, A class of reversible primitive recursive functions, Heuristic methods to use don't cares in automated design of reversible and quantum logic circuits, Constructive chaos by cellular automata and possible sources of an arrow of time, Characterizations of one-way general quantum finite automata, Reversible space equals deterministic space, Frontier between decidability and undecidability: A survey, Theory of one-tape linear-time Turing machines, \(\mathcal{MOQA}\); unlocking the potential of compositional static average-case analysis, Quantum mechanical Hamiltonian models of Turing machines, Quantum computation based on retarded and advanced propagation., PhysComp96. Proceedings of the 4th workshop on physics and computation, Boston, MA, USA, November 22--24, 1996, Quantum model of computations: Underlying principles and achievements, Minimum energy requirements of information transfer and computing, Invertible cellular automata: A review, Quantum neural networks, Computational complexity of uniform quantum circuit families and quantum Turing machines, Quantum information as a general paradigm, One-way reversible multi-head finite automata, A quantum algorithm using NMR computers to break secret-key cryptosystems, Generic conversion method for various spatial domain filters in quantum image processing, Qudits representations and computations of \(n\)-player many-valued quantum games, Efficient exhaustive listings of reversible one dimensional cellular automata, The complexity of reversible cellular automata, Reversible effects as inverse arrows, Efficient and exact quantum compression, Toward efficient design of reversible logic gates in quantum-dot cellular automata with power dissipation analysis, Controlled reversibility in communicating reaction systems, Improving the quantum cost of reversible Boolean functions using reorder algorithm, Energy complexity of regular language recognition, On design of parity preserving reversible adder circuits, Entropy flow in near-critical quantum circuits, Reversible Watson-Crick automata, Reversibility problem of multidimensional finite cellular automata, Concrete resource analysis of the quantum linear-system algorithm used to compute the electromagnetic scattering cross section of a 2D target, An efficient design for reversible Wallace unsigned multiplier, Reversible computation in term rewriting, The complexity of translationally invariant spin chains with low local dimension, Reversible spiking neural P systems, Logical depth for reversible Turing machines with an application to the rate of decrease in logical depth for general Turing machines, Time evolution of complexity: a critique of three methods, A unification of probabilistic choice within a design-based model of reversible computation, Computing the number of the equivalence classes for reversible logic functions, Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3, Quantum speed-up for unsupervised learning, Optimization approaches for designing a novel 4-bit reversible comparator, Efficient classical simulation of the Deutsch-Jozsa and Simon's algorithms, An axiomatic approach to reversible computation, Optimized 4-bit quantum reversible arithmetic logic unit, Towards quantum reversible ternary coded decimal adder, Designing novel quaternary quantum reversible subtractor circuits, The computer as a physical system: a microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines, Space-bounded quantum complexity, Reversibility of computations in graph-walking automata, A parametric framework for reversible \(\pi\)-calculi, A novel design of 8-bit adder/subtractor by quantum-dot cellular automata, Automata theory based on quantum logic: reversibilities and pushdown automata, Epistemic horizons and the foundations of quantum mechanics, Shannon logic based novel QCA full adder design with energy dissipation analysis, Modular design of ultra-efficient reversible full adder-subtractor in QCA with power dissipation analysis, The bouncing ball and the Grünwald-Letnikov definition of fractional derivative, Simulating reversible computation with reaction systems, Reversible computation in nature inspired rule-based systems, Theory of reaction automata: a survey, T-count optimized Wallace tree integer multiplier for quantum computing, Designing of parity preserving reversible vedic multiplier, Multi-strategy based quantum cost reduction of linear nearest-neighbor quantum circuit, A class of recursive permutations which is primitive recursive complete, Image classification based on quantum K-nearest-neighbor algorithm, Continuity of information transport in surjective cellular automata, Information loss as a foundational principle for the second law of thermodynamics, Quantum-enhanced feature selection with forward selection and backward elimination, Word problem for deterministic and reversible semi-Thue systems, Reversible pushdown automata, Quantum walks: a comprehensive review, On one application of computations with oracle, On the origin of ambiguity in efficient communication, Sequential and maximally parallel multiset rewriting: reversibility and determinism, Computational universes, The physics of implementing logic: Landauer's principle and the multiple-computations theorem, Uniformity of quantum circuit families for error-free algorithms, On the computational power of molecular heat engines, Brownian computation is thermodynamically irreversible, Theory of cellular automata: a survey, Determination of equivalence between quantum sequential machines, A theory of reversibility for Erlang, Negative feedback and physical limits of genes, Classical concepts in quantum programming, Fuzzy propositional logic associated with quantum computational gates, Canonical mixed-polarity multi-target Toffoli circuits: shift and removal, Thermodynamics of natural selection. I: Energy flow and the limits on organization, Thermodynamics of natural selection. III: Landauer's principle in computation and chemistry, Nullstellensatz size-degree trade-offs from reversible pebbling, Reversible parallel communicating finite automata systems, An instruction set for reversible Turing machines, Reversibility for stateless ordered RRWW-automata, On entropy and reversibility of pushdown dynamical systems, Binary-decision-diagram-based decomposition of Boolean functions into reversible logic elements, The word problem of the Brin-Thompson group is \textsf{coNP}-complete, Key establishment à la Merkle in a quantum world, Quaternary quantum/reversible half-adder, full-adder, parallel adder and parallel adder/subtractor circuits, An improved design of \(n\)-bit universal reversible gate library, Effective designs of reversible Vedic multiplier, Cost optimization technique for quantum circuits, Gliders in the game of life and in a reversible cellular automaton, Reversible elementary triangular partitioned cellular automata and their complex behavior, A novel and efficient square root computation quantum circuit for floating-point standard, Ergodic quantum computing, On the interpretation of energy as the rate of quantum computation, The \(\aleph \)-calculus. A declarative model of reversible programming, Computing with quanta -- impacts of quantum theory on computation., Quantum implementation and resource estimates for rectangle and knot, Regular languages accepted by quantum automata, Novel design for reversible arithmetic logic unit, Mathematical models of quantum computation, Novel qutrit circuit design for multiplexer, de-multiplexer, and decoder, One complexity theorist's view of quantum computing, Optimal designs of reversible/quantum decoder circuit using new quantum gates, Reversible modified reconstructability analysis of Boolean circuits and its quantum computation, Reversible arithmetic logic unit for quantum arithmetic, Improved Quantum Circuits for Elliptic Curve Discrete Logarithms, Towards Bridging Time and Causal Reversibility, The Complexity of Small Universal Turing Machines: A Survey, Intrinsic universality of a 1-dimensional reversible Cellular Automaton, Decidability Versus Undecidability of the Word Problem in Amalgams of Inverse Semigroups, Improved reversible and quantum circuits for Karatsuba-based integer multiplication., The Classification of Reversible Bit Operations, One-Way Reversible Multi-head Finite Automata, A Deterministic Two-Way Multi-head Finite Automaton Can Be Converted into a Reversible One with the Same Number of Heads, Frugal Encoding in Reversible $\mathcal{MOQA}$ : A Case Study for Quicksort, Design of an Online Testable Ternary Circuit from the Truth Table, Design of a novel quantum reversible ternary up-counter, Digital mechanics. An information process based on reversible universal cellular automata, An 8-State Simple Reversible Triangular Cellular Automaton that Exhibits Complex Behavior, Design and Fabrication of CSWAP Gate Based on Nano-Electromechanical Systems, Application of Permutation Group Theory in Reversible Logic Synthesis, Generating Reversible Circuits from Higher-Order Functional Programs, Reversibility in space-bounded computation, Universality of 8-State Reversible and Conservative Triangular Partitioned Cellular Automata, Aspects of Reversibility for Classical Automata, How Can We Construct Reversible Machines Out of Reversible Logic Element with Memory?, An RNA-based theory of natural universal computation, Quantitative Analysis of Concurrent Reversible Computations, Reversible Limited Automata, Reversible and Irreversible Computations of Deterministic Finite-State Devices, An investigation on support vector clustering for big data in quantum paradigm, Model Theoretic Complexity of Automatic Structures (Extended Abstract), Automata Presenting Structures: A Survey of the Finite String Case, Quantum speedup for pool-based active learning, Some undecidability results for asynchronous transducers and the Brin-Thompson group $2V$, Towards designing quantum reversible ternary multipliers, Design of a fault-tolerant reversible control unit in molecular quantum-dot cellular automata, Reversible computing from a programming language perspective, Minimal Reversible Deterministic Finite Automata, When input-driven pushdown automata meet reversiblity, Injection Structures Specified by Finite State Transducers, Quantum trapping conditions for three-level atom flying through bimodal cavity field, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Undecidable event detection problems for ODEs of dimension one and two, Time-Complexity of the Word Problem for Semigroups and the Higman Embedding Theorem, Lower Bounds for Generalized Quantum Finite Automata, An Asynchronous Cellular Automaton Implementing 2-State 2-Input 2-Output Reversed-Twin Reversible Elements, Parallel Optimization of a Reversible (Quantum) Ripple-Carry Adder, Can a Quantum Computer Run the von Neumann Architecture?, The many faces of the second law, Mutual entropy production in bipartite systems, Quantum Reversible Fuzzy Grammars, Horizons of cybernetical physics, P/NP , and the quantum field computer, NOVEL REVERSIBLE FAULT TOLERANT ERROR CODING AND DETECTION CIRCUITS, Some natural decision problems in automatic graphs, On synthesis of 3 × 3 reversible logic functions, The monoidal structure of Turing machines, Quantum attacks on pseudorandom generators, The Arrow of Time through the Lens of Computing, Number-Conserving Reversible Cellular Automata and Their Computation-Universality, MULTISCALE COMPLEXITY/ENTROPY, A categorical foundation for structured reversible flowchart languages: Soundness and adequacy, Periodicity and Immortality in Reversible Computing, Universality of Reversible Hexagonal Cellular Automata, Computing with Semirings and Weak Rig Groupoids, Efficient Turing-Universal Computation with DNA Polymers, Quantum computation and quantum information†, Cheap Newton steps for optimal control problems: automatic differentiation and Pantoja's algorithm, Join Inverse Categories as Models of Reversible Recursion, NOVEL QUANTUM COMPRESSOR DESIGNS USING NEW GENETIC ALGORITHM-BASED SIMULATOR, ANALYZER AND SYNTHESIZER SOFTWARE IN NANOTECHNOLOGY, An improved Landauer principle with finite-size corrections, ON THE QUANTUM KOLMOGOROV COMPLEXITY OF CLASSICAL STRINGS, Real-Time Methods in Reversible Computation, Reversible Ordered Restarting Automata, MEASUREMENT-BASED QUANTUM COMPUTATION WITH CLUSTER STATES, New dimensions in non‐classical neural computing, part II: quantum, nano, and optical, Circuits form‐valued classical, reversible and quantum optical computing with application to regular logic design, New dimensions in non‐classical neural computing, Unnamed Item, Partial Observation of Quantum Turing Machines and a Weaker Well-Formedness Condition, Quantum Automata Theory – A Review, Minimal and Reduced Reversible Automata, A Certified Study of a Reversible Programming Language, Boolean satisfiability in quantum compilation, Bicontinuous extensions of invertible combinatorial functions, Primality Test Via Quantum Factorization, Necessary and Sufficient Conditions for Quantum Computation, Quantum Perceptrons, Oracle Quantum Computing, Realizable Universal Quantum Logic Gates, Mutation systems, A theory of computation based on quantum logic. I, Natural limitations of decision procedures for arithmetic with bounded quantifiers, A structural approach to reversible computation, Quantum Programming With Mixed States, Computation in reversible cellular automata, From Reversible to Irreversible Computations, A Survey on Analog Models of Computation, The physics of quantum computation
