Reversible space equals deterministic space
From MaRDI portal
Publication:1567403
DOI10.1006/jcss.1999.1672zbMath0956.68057OpenAlexW2136462002WikidataQ56028833 ScholiaQ56028833MaRDI QIDQ1567403
Pierre McKenzie, Alain Tapp, Klaus-Joern Lange
Publication date: 5 June 2000
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/2aefe765dcbcf8ec6b7198114f2a9f129bee5bce
Related Items
Improved reversible and quantum circuits for Karatsuba-based integer multiplication. ⋮ A Deterministic Two-Way Multi-head Finite Automaton Can Be Converted into a Reversible One with the Same Number of Heads ⋮ Toward an Energy Efficient Language and Compiler for (Partially) Reversible Algorithms ⋮ Reversibility in space-bounded computation ⋮ Lamplighter groups and automata ⋮ Aspects of Reversibility for Classical Automata ⋮ Reversible Limited Automata ⋮ Reversible and Irreversible Computations of Deterministic Finite-State Devices ⋮ Unnamed Item ⋮ Descriptive Complexity of Reversible Languages Having Finitely Many Reduced Automata ⋮ Weakly and Strongly Irreversible Regular Languages ⋮ Energy complexity of computation ⋮ Computational complexity of reversible reaction systems ⋮ Queue Automata: Foundations and Developments ⋮ State complexity of transforming graph-walking automata to halting, returning and reversible ⋮ Energy complexity of regular languages ⋮ Reversible computing from a programming language perspective ⋮ When input-driven pushdown automata meet reversiblity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Reversibility of computations in graph-walking automata ⋮ Unnamed Item ⋮ The bouncing ball and the Grünwald-Letnikov definition of fractional derivative ⋮ Quantum branching programs and space-bounded nonuniform quantum complexity ⋮ Quantum versus deterministic counter automata ⋮ Rush Hour is PSPACE-complete, or ``Why you should generously tip parking lot attendants ⋮ Concise Representations of Reversible Automata ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling ⋮ Unnamed Item ⋮ Transducing reversibly with finite state machines ⋮ Transducing reversibly with finite state machines ⋮ A hybrid algorithm framework for small quantum computers with application to finding Hamiltonian cycles ⋮ On the power of two-way multihead quantum finite automata ⋮ A Hierarchy of Fast Reversible Turing Machines ⋮ Real-Time Methods in Reversible Computation ⋮ Minimal and Reduced Reversible Automata ⋮ Nullstellensatz size-degree trade-offs from reversible pebbling ⋮ Real-Time Reversible One-Way Cellular Automata ⋮ Language Recognition by Reversible Partitioned Cellular Automata
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Reversible simulation of space-bounded computations
- Halting space-bounded computations
- Symmetric space-bounded computation
- Computer science today. Recent trends and developments
- Reversibility and adiabatic computation: trading time and space for energy
- A Note on Bennett’s Time-Space Tradeoff for Reversible Computation
- Irreversibility and Heat Generation in the Computing Process
- A taxonomy of problems with fast parallel algorithms
- Problems complete for deterministic logarithmic space
- Time/Space Trade-Offs for Reversible Computation
- Quantum theory, the Church–Turing principle and the universal quantum computer
- Logical Reversibility of Computation
This page was built for publication: Reversible space equals deterministic space
