Deterministic two-dimensional on-line tessellation acceptors are equivalent to two-way two-dimensional alternating finite automata through 180\(\circ\)-rotation
From MaRDI portal
Publication:1822982
DOI10.1016/0304-3975(89)90154-0zbMath0679.68104OpenAlexW2050997354MaRDI QIDQ1822982
Itsuo Takanami, Akira Ito, Katsushi Inoue
Publication date: 1989
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(89)90154-0
Related Items (8)
A survey of two-dimensional automata theory ⋮ Two-dimensional cellular automata and deterministic on-line tessalation automata ⋮ Characterization of real time iterative array by alternating device. ⋮ Deterministic Two-Dimensional Languages over One-Letter Alphabet ⋮ Optimal simulation of two-dimensional alternating finite automata by three-way nondeterministic Turing machines ⋮ Deterministic and unambiguous two-dimensional languages over one-letter alphabet ⋮ A Survey on Picture-Walking Automata ⋮ Some results concerning 2-D on-line tessellation acceptors and 2-D alternating finite automata
Cites Work
- Two-dimensional alternative Turing machines
- A space-hierarchy result on two-dimensional alternating Turing machines with only universal states
- A note on three-way two dimensional alternating Turing machines
- Some properties of two-dimensional on-line tessellation acceptors
- Two-dimensional alternating turing machines with only universal states
This page was built for publication: Deterministic two-dimensional on-line tessellation acceptors are equivalent to two-way two-dimensional alternating finite automata through 180\(\circ\)-rotation