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
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (22)
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 ⋮ 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
Cites Work
This page was built for publication: On alternation
