Deterministic two-dimensional on-line tessellation acceptors are equivalent to two-way two-dimensional alternating finite automata through 180-rotation
A two-way two-dimensional alternating finite automaton (TW2-AFA) is a two-dimensional alternating finite automaton [see the second and third author with \textit{H. Taniguchi}; Theor. Comput. Sci. 27, 61-83 (1983; Zbl 0539.68039)] whose input head can move right and down (or may not move). A two-dimensional deterministic on-line tesselation acceptor (2-dota) is a two-dimensional on-line tesselation acceptor [see the second author and \textit{A. Nakamura}; Inform. Sci. 13, 95-121 (1977; Zbl 0371.94067)] whose the cell state function is a singleton. It is proved that 2-dota's are equivalent to TW2-AFA's through 180\(\circ\)-rotation.
- scientific article; zbMATH DE number 176142
- Two-dimensional alternative Turing machines
- Some results concerning 2-D on-line tessellation acceptors and 2-D alternating finite automata
- Two-dimensional automata with rotated inputs (projection-type)
- Two-dimensional cellular automata and deterministic on-line tessalation automata
- A note on three-way two dimensional alternating Turing machines
- A space-hierarchy result on two-dimensional alternating Turing machines with only universal states
- Some properties of two-dimensional on-line tessellation acceptors
- Two-dimensional alternating turing machines with only universal states
- Two-dimensional alternative Turing machines
- Deterministic and unambiguous two-dimensional languages over one-letter alphabet
- Some results concerning 2-D on-line tessellation acceptors and 2-D alternating finite automata
- Two-dimensional cellular automata and deterministic on-line tessalation automata
- Characterization of real time iterative array by alternating device.
- A survey of two-dimensional automata theory
- A survey on picture-walking automata
- Deterministic Two-Dimensional Languages over One-Letter Alphabet
- scientific article; zbMATH DE number 176142 (Why is no real title available?)
- Optimal simulation of two-dimensional alternating finite automata by three-way nondeterministic Turing machines
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
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1822982)
