Two-dimensional alternative Turing machines
From MaRDI portal
Publication:794169
DOI10.1016/0304-3975(83)90093-2zbMath0539.68039MaRDI QIDQ794169
Katsushi Inoue, Itsuo Takanami, Hiroshi Taniguchi
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 classes; accepting power; leaf-size; recognizability of connected patterns; space bounded Turing machine; three-way two-dimensional alternating Turing machine; two-dimensional alternating Turing machine
68Q25: Analysis of algorithms and problem complexity
Related Items
A NOTE ON REBOUND TURING MACHINES, A note on one-pebble two-dimensional Turing machines, A note on one-pebble two-dimensional Turing machines, Optimal simulation of two-dimensional alternating finite automata by three-way nondeterministic Turing machines, A computational model for tiling recognizable two-dimensional languages, A note on time-bounded bottom-up pyramid cellular acceptors, Deterministic and unambiguous two-dimensional languages over one-letter alphabet, A space-hierarchy result on two-dimensional alternating Turing machines with only universal states, Alternating simple multihead finite automata, 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, A hierarchy result for 2-dimensional TM's operating in small space, A note on two-dimensional probabilistic finite automata, A note on three-dimensional alternating Turing machines with space smaller than \(\log m\), Some results concerning 2-D on-line tessellation acceptors and 2-D alternating finite automata, 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 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, Non-closure property of space-bounded two-dimensional alternating Turing machines, Three-way two-dimensional alternating finite automata with rotated inputs, A survey of two-dimensional automata theory, A Survey on Picture-Walking Automata, Tiling Automaton: A Computational Model for Recognizable Two-Dimensional Languages, Deterministic Two-Dimensional Languages over One-Letter Alphabet
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
