Turing machines with access to history

DOI10.1016/0890-5401(90)90008-6MaRDI QIDQ751802zbMATHOpenAlexFDO

Authors Bogdan S. Chlebus

Publication date 1990

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0890-5401(90)90008-6

zbMATH Keywords

remembering Turing machines

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• On the Computational Power of Querying the History
• scientific article; zbMATH DE number 3850476
• scientific article; zbMATH DE number 3984575
• On reversal bounded alternating Turing machines
• A hierarchy of fast reversible Turing machines

Cites work

• scientific article; zbMATH DE number 3976339 (Why is no real title available?)
• scientific article; zbMATH DE number 4039295 (Why is no real title available?)
• scientific article; zbMATH DE number 4061218 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3727583 (Why is no real title available?)
• scientific article; zbMATH DE number 3894472 (Why is no real title available?)
• N by N Checkers is Exptime Complete
• Alternation
• Alternation with restrictions on looping
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• Domino-tiling games
• GO Is Polynomial-Space Hard
• Solitaire automata
• The complexity of two-player games of incomplete information
• Writing pushdown acceptors

This page was built for publication: Turing machines with access to history

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