Reversibility in space-bounded computation

DOI10.1080/03081079.2014.920998MaRDI QIDQ2930716zbMATH OpenOpenAlexFDO

Authors Kenichi Morita

Publication date 19 November 2014

Published in International Journal of General Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/03081079.2014.920998

zbMATH Keywords

reversibilitydeterminismspace complexityreversible computingspace-bounded Turing machinesymmetric Turing machine

Mathematics Subject Classification ID

Recommendations

• Reversible simulation of space-bounded computations
• Time/Space Trade-Offs for Reversible Computation
• A Note on Bennett’s Time-Space Tradeoff for Reversible Computation
• Time and space bounds for reversible simulation
• A structural approach to reversible computation
• An axiomatic approach to reversible computation
• scientific article; zbMATH DE number 1754652
• Reversal complexity revisited
• scientific article; zbMATH DE number 1189113
• Reversible computation in term rewriting

Cites work

• Irreversibility and Heat Generation in the Computing Process
• Logical Reversibility of Computation
• Reversible space equals deterministic space
• Symmetric space-bounded computation
• Time/Space Trade-Offs for Reversible Computation
• Undirected connectivity in log-space

Cited in

(13)

• Reversibility of computations in graph-walking automata
• Quantitative Analysis of Concurrent Reversible Computations
• Reverse complexity
• Reversible parallel computation: An evolving space-model
• GENERALIZED COUNTERS AND REVERSAL COMPLEXITY
• A structural approach to reversible computation
• Reversible simulation of space-bounded computations
• Time complexity of tape reduction for reversible Turing machines
• Reversible space equals deterministic space
• Time and space complexity of reversible pebbling
• Verified compilation of space-efficient reversible circuits
• A hierarchy of fast reversible Turing machines
• Sublogarithmic Bounds on Space and Reversals

This page was built for publication: Reversibility in space-bounded computation

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