Optimal simulation of two-dimensional alternating finite automata by three-way nondeterministic Turing machines
From MaRDI portal
Publication:673641
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)
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