On alternation. II. A graph theoretic approach to determinism versus nondeterminism
From MaRDI portal
Publication:1146515
zbMath0447.68043MaRDI QIDQ1146515
Wolfgang J. Paul, K. Ruediger Reischuk
Publication date: 1980
Published in: Acta Informatica (Search for Journal in Brave)
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (13)
On the structure of one-tape nondeterministic Turing machine time hierarchy ⋮ Speedup of determinism by alternation for multidimensional Turing machines ⋮ Cumulative Space in Black-White Pebbling and Resolution ⋮ Nonuniform ACC Circuit Lower Bounds ⋮ Amplifying circuit lower bounds against polynomial time, with applications ⋮ Three-dimensional alternating Turing machines with only universal states ⋮ Parallelizing time with polynomial circuits ⋮ Towards separating nondeterminism from determinism ⋮ Alternating time versus deterministic time: A separation ⋮ A note on alternating on-line Turing machines ⋮ Two-dimensional alternative Turing machines ⋮ Depth-Robust Graphs and Their Cumulative Memory Complexity ⋮ Speedups of deterministic machines by synchronous parallel machines
This page was built for publication: On alternation. II. A graph theoretic approach to determinism versus nondeterminism
