On the power of alternation in automata theory
From MaRDI portal
Publication:1068537
DOI10.1016/0022-0000(85)90063-7zbMath0582.68018OpenAlexW2077819737MaRDI QIDQ1068537
Publication date: 1985
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(85)90063-7
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (14)
Deterministic versus nondeterministic space in terms of synchronized alternating machines ⋮ Tradeoffs for language recognition on alternating machines ⋮ Constructions for alternating finite automata∗ ⋮ A grammatical characterization of alternating pushdown automata ⋮ Lower bounds for language recognition on two-dimensional alternating multihead machines ⋮ Converting finite width AFAs to nondeterministic and universal finite automata ⋮ Existential and universal width of alternating finite automata ⋮ On space-bounded synchronized alternating Turing machines ⋮ A characterization of exponential-time languages by alternating context- free grammars ⋮ Communication for alternating machines ⋮ Unnamed Item ⋮ A leaf-time hierarchy of two-dimensional alternating turing machines ⋮ Separation of deterministic, nondeterministic and alternating complexity classes ⋮ A note on real-time one-way alternating multicounter machines
Cites Work
This page was built for publication: On the power of alternation in automata theory