A Hierarchy of Fast Reversible Turing Machines

DOI10.1007/978-3-319-20860-2_2zbMath1464.68103OpenAlexW1134399418MaRDI QIDQ2822488

Andreas Malcher, Martin Kutrib, Sebastian Jakobi, Holger Bock Axelsen

Publication date: 30 September 2016

Published in: Reversible Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-20860-2_2

zbMATH Keywords

fast computationstime hierarchiesreversible Turing machinesreal time vs. linear timestructural computational complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Other nonclassical models of computation (68Q09) Classical models of computation (Turing machines, etc.) (68Q04)

Related Items

On reversible Turing machines and their function universality, Boosting Reversible Pushdown Machines by Preprocessing, Reversible and Irreversible Computations of Deterministic Finite-State Devices, Unnamed Item, Reversible pushdown transducers, Transducing reversibly with finite state machines, Transducing reversibly with finite state machines, Boosting Reversible Pushdown and Queue Machines by Preprocessing

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reversible space equals deterministic space
• Deterministic Turing machines in the range between real-time and linear-time.
• Time Complexity of Tape Reduction for Reversible Turing Machines
• Reversible Turing Machines and Polynomial Time Reversibly Computable Functions
• Time/Space Trade-Offs for Reversible Computation
• On the Computational Complexity of Algorithms
• Real-Time Definable Languages
• Real-Time Computation by n-Dimensional Iterative Arrays of Finite-State Machines
• One-tape, off-line Turing machine computations