Two-dimensional alternative Turing machines
From MaRDI portal
Publication:794169
DOI10.1016/0304-3975(83)90093-2zbMath0539.68039OpenAlexW1967725522MaRDI QIDQ794169
Itsuo Takanami, Hiroshi Taniguchi, Katsushi Inoue
Publication date: 1983
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(83)90093-2
complexity classesaccepting powerleaf-sizerecognizability of connected patternsspace bounded Turing machinethree-way two-dimensional alternating Turing machinetwo-dimensional alternating Turing machine
Related Items (26)
A computational model for tiling recognizable two-dimensional languages ⋮ A survey of two-dimensional automata theory ⋮ A note on three-way two dimensional alternating Turing machines ⋮ Lower bounds for language recognition on two-dimensional alternating multihead machines ⋮ Three-dimensional alternating Turing machines with only universal states ⋮ Tiling Automaton: A Computational Model for Recognizable Two-Dimensional Languages ⋮ Deterministic Two-Dimensional Languages over One-Letter Alphabet ⋮ A note on time-bounded bottom-up pyramid cellular acceptors ⋮ A note on one-pebble two-dimensional Turing machines ⋮ Optimal simulation of two-dimensional alternating finite automata by three-way nondeterministic Turing machines ⋮ A note on one-pebble two-dimensional Turing machines ⋮ A hierarchy result for 2-dimensional TM's operating in small space ⋮ Three-way two-dimensional alternating finite automata with rotated inputs ⋮ A NOTE ON REBOUND TURING MACHINES ⋮ Deterministic and unambiguous two-dimensional languages over one-letter alphabet ⋮ Closure properties of the classes of sets recognized by space-bounded two-dimensional probabilistic Turing machines ⋮ A note on two-dimensional probabilistic Turing machines ⋮ A Survey on Picture-Walking Automata ⋮ 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 ⋮ A note on two-dimensional probabilistic finite automata ⋮ A space-hierarchy result on two-dimensional alternating Turing machines with only universal states ⋮ Alternating simple multihead finite automata ⋮ A note on three-dimensional alternating Turing machines with space smaller than \(\log m\) ⋮ Non-closure property of space-bounded two-dimensional alternating Turing machines ⋮ Some results concerning 2-D on-line tessellation acceptors and 2-D alternating finite automata
Cites Work
- Unnamed Item
- Unnamed Item
- A note on closure properties of the classes of sets accepted by tape- bounded two-dimensional Turing machines
- On alternation
- Three-way tape-bounded two-dimensional Turing machines
- Closure properties of three-way and four-way tape-bounded two-dimensional Turing machines
- Real-time recognition of two-dimensional tapes by cellular automata
- Tree-size bounded alternation
- On alternation. II. A graph theoretic approach to determinism versus nondeterminism
- A note on deterministic three-way tape-bounded two-dimensional Turing machines
- Some properties of two-dimensional on-line tessellation acceptors
- Two-dimensional alternating turing machines with only universal states
- Alternation
- One-Pass Complexity of Digital Picture Properties
This page was built for publication: Two-dimensional alternative Turing machines
