-type automata (obtained by combining four tr2-dfa's in "and" fashion). We first investigate a relationship between the accepting powers of
For Full-Text PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Three-Way Two-Dimensional Deterministic Finite Automata with Rotated Inputs
Hisao HIRAKAWA Katsushi INOUE Akira ITO
IEICE TRANSACTIONS on Information and Systems Vol.E88-D No.1 pp.31-38
Publication Date: 2005/01/01
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)
two-dimensional tape, three-way deterministic finite automata, rotated inputs,
Full Text: PDF(536.3KB)
>>Buy this Article
Inoue et al. 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 various automata which move one way, and investigated the accepting power of such an automaton. This paper continues the investigation of this type of automata, especially, -type automata (obtained by combining four three-way two-dimensional deterministic finite automata (tr2-dfa's) in "or" fashion) and -type automata (obtained by combining four tr2-dfa's in "and" fashion). We first investigate a relationship between the accepting powers of -type automata and -type automata, and show that they are incomparable. Then, we investigate a hierarchy of the accepting powers based on the number of tr2-dfa's combined. Finally, we briefly describe a relationship between the accepting powers of automata obtained by combining three-way two-dimensional deterministic and nondeterministic finite automata.