A leaf-time hierarchy of two-dimensional alternating turing machines
From MaRDI portal
Publication:1822969
DOI10.1016/0304-3975(89)90025-XzbMath0679.68085OpenAlexW2098244358MaRDI QIDQ1822969
Itsuo Takanami, Katsushi Inoue, Juraj Hromkovič
Publication date: 1989
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(89)90025-x
hierarchycomplexity measureleaf-size bounded computationsspace bounded two-dimensional alternating Turing machines
Cites Work
- A note on alternating on-line Turing machines
- Two-dimensional alternative Turing machines
- A space-hierarchy result on two-dimensional alternating Turing machines with only universal states
- On the power of alternation in automata theory
- On alternation
- Three-way tape-bounded two-dimensional Turing machines
- Tree-size bounded alternation
- Two-dimensional alternating turing machines with only universal states
- Alternation