Turing machines with access to history
From MaRDI portal
Publication:751802
DOI10.1016/0890-5401(90)90008-6zbMath0715.68023OpenAlexW2023618654MaRDI QIDQ751802
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
Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- The complexity of two-player games of incomplete information
- Solitaire automata
- Domino-tiling games
- Writing pushdown acceptors
- N by N Checkers is Exptime Complete
- Alternation with restrictions on looping
- GO Is Polynomial-Space Hard
- Alternation
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
