Separation of deterministic, nondeterministic and alternating complexity classes

DOI10.1016/0304-3975(91)90379-GzbMath0733.68029OpenAlexW1981385397MaRDI QIDQ809596

Andrej Bebják, Ivana Štefáneková

Publication date: 1991

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(91)90379-g

zbMATH Keywords

Turing machineslower boundnondeterminismalternation

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Unnamed Item
• Unnamed Item
• On the power of alternation in automata theory
• One way multihead deterministic finite automata
• A time-space tradeoff for language recognition
• k + 1 Heads Are Better than k

This page was built for publication: Separation of deterministic, nondeterministic and alternating complexity classes