Two-dimensional alternating turing machines with only universal states

DOI10.1016/S0019-9958(82)90572-1zbMath0557.68037OpenAlexW2088973818MaRDI QIDQ3221411

Itsuo Takanami, K. Inone, Hiroshi Taniguchi, Akira Ito

Publication date: 1982

Published in: Information and Control (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0019-9958(82)90572-1

zbMATH Keywords

accepting power

Mathematics Subject Classification ID

Related Items (21)

Three-way two-dimensional finite automata with rotated inputs ⋮ Simulation of three-dimensional one-marker automata by five-way Turing machines ⋮ Alternating on-line Turing machines with only universal states and small space bounds ⋮ A survey of two-dimensional automata theory ⋮ A note on three-way two dimensional alternating Turing machines ⋮ On the power of nondeterminism and Las Vegas randomization for two-dimensional finite automata ⋮ Lower bounds for language recognition on two-dimensional alternating multihead machines ⋮ Three-dimensional alternating Turing machines with only universal states ⋮ A note on one-pebble two-dimensional Turing machines ⋮ Some properties of space-bounded synchronized alternating Turing machines with universal states only ⋮ 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 ⋮ On space-bounded synchronized alternating 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 ⋮ Two-dimensional alternative Turing machines ⋮ A space-hierarchy result on two-dimensional alternating Turing machines with only universal states ⋮ 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

This page was built for publication: Two-dimensional alternating turing machines with only universal states