Three-way two-dimensional alternating finite automata with rotated inputs

摘要

The authors have introduced an automaton on a two-dimensional tape, which decides acceptance or rejection of an input tape by scanning the tape from various sides by three-way (deterministic and nondeterministic) finite automata, and have investigated the accepting powers. This paper continues the investigation of this type of automata, which consists of four three-way two-dimensional alternating finite automata (tr2-afa's). We first investigate a relationship between the accepting powers of V-type automata (obtained by combining tr2-afa's in 'or' fashion) and A-type automata (obtained by combining tr2-afa's in 'and' fashion), and show that they are incomparable. Then, we investigate a hierarchy of the accepting powers based on the number of tr2-afa's combined. Finally, we briefly describe a relationship between the accepting powers of automata obtained by combining three-way two-dimensional nondeterministic and alternating finite automata. (C) 2005 Elsevier Inc. All rights reserved.