A space-hierarchy result on two-dimensional alternating Turing machines with only universal states
From MaRDI portal
Publication:1057650
DOI10.1016/0020-0255(85)90042-8zbMath0563.68045OpenAlexW2112208288MaRDI QIDQ1057650
Itsuo Takanami, Akira Ito, Katsushi Inoue, Hiroshi Taniguchi
Publication date: 1985
Published in: Information Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0255(85)90042-8
alternating Turing machinesinfinite hierarchy of space complexity classesspace constructible functions
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)
Related Items
A note on three-way two dimensional alternating Turing machines ⋮ Lower bounds for language recognition on two-dimensional alternating multihead machines ⋮ Some properties of space-bounded synchronized alternating Turing machines with universal states only ⋮ A hierarchy result for 2-dimensional TM's operating in small space ⋮ On space-bounded synchronized alternating Turing machines ⋮ A leaf-time hierarchy of two-dimensional alternating turing machines ⋮ Deterministic two-dimensional on-line tessellation acceptors are equivalent to two-way two-dimensional alternating finite automata through 180\(\circ\)-rotation ⋮ Some results concerning 2-D on-line tessellation acceptors and 2-D alternating finite automata
Cites Work
- Unnamed Item
- Unnamed Item
- Two-dimensional alternative Turing machines
- A note on closure properties of the classes of sets accepted by tape- bounded two-dimensional Turing machines
- Three-way tape-bounded two-dimensional Turing machines
- Techniques for separating space complexity classes
- Relating refined space complexity classes
- Two-dimensional alternating turing machines with only universal states
- Some Results on Tape-Bounded Turing Machines
This page was built for publication: A space-hierarchy result on two-dimensional alternating Turing machines with only universal states
