
For FullText 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.

ThreeWay TwoDimensional Deterministic Finite Automata with Rotated Inputs
Hisao HIRAKAWA Katsushi INOUE Akira ITO
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E88D
No.1
pp.3138 Publication Date: 2005/01/01
Online ISSN:
DOI: 10.1093/ietisy/e88d.1.31
Print ISSN: 09168532 Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science) Category: Keyword: twodimensional tape, threeway deterministic finite automata, rotated inputs,
Full Text: PDF(536.3KB) >>Buy this Article
Summary:
Inoue et al. introduced an automaton on a twodimensional 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 threeway twodimensional deterministic finite automata (tr2dfa's) in "or" fashion) and type automata (obtained by combining four tr2dfa'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 tr2dfa's combined. Finally, we briefly describe a relationship between the accepting powers of automata obtained by combining threeway twodimensional deterministic and nondeterministic finite automata.

