A note on some simultaneous relations among time, space, and reversal for single work tape nondeterministic turing machines

DOI10.1016/S0019-9958(86)80003-1zbMath0623.68051OpenAlexW2025399640MaRDI QIDQ3761700

Takumi Kasai, Shigeki Iwata, Etsuro Moriya

Publication date: 1986

Published in: Information and Control (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0019-9958(86)80003-1

zbMATH Keywords

nondeterministic single worktape off-line Turing machinesreversal- space bounded classesSimultaneous resource bounded complexity classestime-reversal bounded classestime-space bounded classes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (2)

Reversal-space trade-offs for simultaneous resource-bounded nondeterministic Turing machines ⋮ Relations among simultaneous complexity classes of nondeterministic and alternating Turing machines

This page was built for publication: A note on some simultaneous relations among time, space, and reversal for single work tape nondeterministic turing machines