On the Power of Two-Dimensional Synchronized Alternating Finite Automata1

DOI Open Access

Search this article

Description

<jats:p>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.</jats:p>

Journal

Details 詳細情報について

Report a problem

Back to top