Optimal simulation of two-dimensional alternating finite automata by three-way nondeterministic Turing machines

DOI10.1016/0304-3975(95)80014-XzbMath0873.68136MaRDI QIDQ673641

Akira Ito, Yue Wang, Itsuo Takanami, Katsushi Inoue

Publication date: 28 February 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

three-way nondeterministic Turing machines

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)

Cites Work

• Unnamed Item
• Two-dimensional alternative Turing machines
• Some results concerning 2-D on-line tessellation acceptors and 2-D alternating finite automata
• Deterministic two-dimensional on-line tessellation acceptors are equivalent to two-way two-dimensional alternating finite automata through 180\(\circ\)-rotation
• Two-dimensional alternating turing machines with only universal states
• Alternation