Deterministic two-dimensional on-line tessellation acceptors are equivalent to two-way two-dimensional alternating finite automata through 180\(\circ\)-rotation
type: Item
instance of: scholarly article
title: Deterministic two-dimensional on-line tessellation acceptors are equivalent to two-way two-dimensional alternating finite automata through 180\(\circ\)-rotation
zbMATH Open document ID: 0679.68104
DOI: 10.1016/0304-3975(89)90154-0
author: Akira Ito
author: Katsushi Inoue
author: Itsuo Takanami
published in: Theoretical Computer Science
publication date: 1989-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q80
zbMATH DE Number: 4114028
zbMATH Keywords: tessellation acceptors
zbMATH Keywords: finite automata
zbMATH Keywords: equivalence
MaRDI profile type: Publication
full work available at URL: 0304-3975(89)90154-0
OpenAlex ID: W2050997354
cites work: A space-hierarchy result on two-dimensional alternating Turing machines with only universal states
cites work: Some properties of two-dimensional on-line tessellation acceptors
cites work: Two-dimensional alternative Turing machines
cites work: A note on three-way two dimensional alternating Turing machines
cites work: Two-dimensional alternating turing machines with only universal states
description: scientific article; zbMATH DE number 4114028