On the Power of Two-Dimensional Synchronized Alternating Finite Automata¹

Article type: Research Article

Authors: Hromkovič, Juraj^{a; b} | Inoue, Katsushi^c | Ito, Akira^c | Takanami, Itsuo^c

Affiliations: [a] Department of Computer Science, Comenius University, 842 15 Bratislava, Czechoslovakia | [b] Fachbereich 17, Mathematik-Injormatik, Universität-GH Paderborn, 4790 Paderborn, Germany | [c] Department of Computer Science and Systems Engineering, Faculty of Engineering, Yamaguchi University, Ube, 755 Japan

Note: [1] This paper was made during the stay of the first author at Yamaguchi University.

Abstract: It is well known that four-way two-dimensional alternating finite automata are more powerful than three-way two-dimensional alternating finite automata, which are more powerful than two-way two-dimensional alternating finite automata. This paper shows that four-way, three-way, and two-way two-dimensional “synchronized” alternating finite automata all have the same power as rectangular array bounded automata.

DOI: 10.3233/FI-1991-15108

Journal: Fundamenta Informaticae, vol. 15, no. 1, pp. 90-98, 1991