Time complexity of tape reduction for reversible Turing machines

DOI10.1007/978-3-642-29517-1_1MaRDI QIDQ2902496zbMATH OpenOpenAlexFDO

Authors Holger Bock Axelsen

Publication date 20 August 2012

Published in Reversible Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-29517-1_1

Mathematics Subject Classification ID

Classical models of computation (Turing machines, etc.) (68Q04) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Time/Space Trade-Offs for Reversible Computation
• The difference between one tape and two tapes: With respect to reversal complexity
• A hierarchy of fast reversible Turing machines
• SOFSEM 2004: Theory and Practice of Computer Science
• Reversibility in space-bounded computation

Cited in

(4)

• A hierarchy of fast reversible Turing machines
• On reversible Turing machines and their function universality
• Time and space complexity of reversible pebbling
• Hydrodynamic and symbolic models of computation with advice

This page was built for publication: Time complexity of tape reduction for reversible Turing machines

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