On alternation
From MaRDI portal
Publication:1141480
DOI10.1007/BF00264255zbMath0437.68025OpenAlexW2913527980MaRDI QIDQ1141480
Ernst-Jürgen Prauß, Wolfgang J. Paul, K. Ruediger Reischuk
Publication date: 1980
Published in: Acta Informatica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf00264255
Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)
Cites Work
Related Items (23)
On 1-inkdot alternating Turing machines with small space ⋮ 1998 European Summer Meeting of the Association for Symbolic Logic ⋮ On the structure of one-tape nondeterministic Turing machine time hierarchy ⋮ Alternating on-line Turing machines with only universal states and small space bounds ⋮ On reversal bounded alternating Turing machines ⋮ Alternating real-time computations ⋮ Amplifying circuit lower bounds against polynomial time, with applications ⋮ Constructions for alternating finite automata∗ ⋮ Three-dimensional alternating Turing machines with only universal states ⋮ New time hierarchy results for deterministic TMS ⋮ An NP-complete language accepted in linear time by a one-tape Turing machine ⋮ Interactive proof systems and alternating time-space complexity ⋮ Communication for alternating machines ⋮ Lower bounds for multiplayer noncooperative games of incomplete information ⋮ Computational complexity of puzzles and related topics ⋮ Alternating time versus deterministic time: A separation ⋮ A leaf-time hierarchy of two-dimensional alternating turing machines ⋮ Theory of one-tape linear-time Turing machines ⋮ A note on alternating on-line Turing machines ⋮ Two-dimensional alternative Turing machines ⋮ Alternating simple multihead finite automata ⋮ A note on real-time one-way alternating multicounter machines ⋮ Speedups of deterministic machines by synchronous parallel machines
This page was built for publication: On alternation
