Alternating time versus deterministic time: A separation
From MaRDI portal
Publication:4717057
DOI10.1007/BF01301970zbMath0868.68053MaRDI QIDQ4717057
No author found.
Publication date: 17 August 1997
Published in: Mathematical Systems Theory (Search for Journal in Brave)
Related Items
Cites Work
- Unnamed Item
- A Turing machine time hierarchy
- On proving time constructibility of functions
- Speedups of deterministic machines by synchronous parallel machines
- The method of forced enumeration for nondeterministic automata
- On alternation
- On alternation. II. A graph theoretic approach to determinism versus nondeterminism
- A hierarchy for nondeterministic time complexity
- Time- and tape-bounded Turing acceptors and AFLs
- Nondeterministic Space is Closed under Complementation
- Alternation
- On Time Versus Space
- Separating Nondeterministic Time Complexity Classes
- On the Computational Complexity of Algorithms