Alternating on-line Turing machines with only universal states and small space bounds
From MaRDI portal
Publication:1083207
DOI10.1016/0304-3975(85)90080-5zbMath0604.68056OpenAlexW2021044407MaRDI QIDQ1083207
Katsushi Inoue, Roland Vollmar, Itsuo Takanami
Publication date: 1985
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(85)90080-5
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (5)
On 1-inkdot alternating Turing machines with small space ⋮ Some observations concerning alternating Turing machines using small space ⋮ Some properties of space-bounded synchronized alternating Turing machines with universal states only ⋮ On space-bounded synchronized alternating Turing machines ⋮ Alternation for sublogarithmic space-bounded alternating pushdown automata
Cites Work
- Unnamed Item
- A note on alternating on-line Turing machines
- Bandwidth constraints on problems complete for polynomial time
- On alternation
- Tree-size bounded alternation
- An extension of Savitch's theorem to small space bounds
- On tape-bounded complexity classes and multihead finite automata
- Two-dimensional alternating turing machines with only universal states
- Alternation
This page was built for publication: Alternating on-line Turing machines with only universal states and small space bounds
