Reversible simulation of space-bounded computations

DOI10.1016/0304-3975(95)80017-4MaRDI QIDQ673645zbMATHOpenAlexFDO

Authors Pilu Crescenzi, Christos Papadimitriou

Publication date 28 February 1997

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

Full work available at URL https://doi.org/10.1016/0304-3975(95)80017-4

zbMATH Keywords

deterministic Turing machines

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Time and space bounds for reversible simulation
• scientific article; zbMATH DE number 1754652
• Reversibility in space-bounded computation
• Time/Space Trade-Offs for Reversible Computation
• A Note on Bennett’s Time-Space Tradeoff for Reversible Computation
• Verified compilation of space-efficient reversible circuits
• Reversible parallel computation: An evolving space-model
• A structural approach to reversible computation
• Quantitative Analysis of Concurrent Reversible Computations
• Applying reversibility theory for the performance evaluation of reversible computations

Cites work

• A Note on Bennett’s Time-Space Tradeoff for Reversible Computation
• Irreversibility and Heat Generation in the Computing Process
• Logical Reversibility of Computation
• On Relating Time and Space to Size and Depth
• On the complexity of the parity argument and other inefficient proofs of existence
• Quantum complexity theory
• Relationships between nondeterministic and deterministic tape complexities
• Symmetric space-bounded computation
• Time/Space Trade-Offs for Reversible Computation

Cited in

(14)

• Reversibility of computations in graph-walking automata
• Time and space bounds for reversible simulation
• Rush Hour is PSPACE-complete, or ``Why you should generously tip parking lot attendants
• Quantitative Analysis of Concurrent Reversible Computations
• Reversible parallel computation: An evolving space-model
• Real-time methods in reversible computation
• scientific article; zbMATH DE number 1754652 (Why is no real title available?)
• Space-bounded quantum complexity
• Reversible space equals deterministic space
• Reversible computation in term rewriting
• Verified compilation of space-efficient reversible circuits
• Reversibility in space-bounded computation
• Reversible Turing Machines and Polynomial Time Reversibly Computable Functions
• An improved simulation of space and reversal bounded deterministic Turing machines by width and depth bounded uniform circuits

This page was built for publication: Reversible simulation of space-bounded computations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q673645)