Keyword Search Result

[Keyword] rotated inputs(1hit)

1-1hit
  • Three-Way Two-Dimensional Deterministic Finite Automata with Rotated Inputs

    Hisao HIRAKAWA  Katsushi INOUE  Akira ITO  

     
    PAPER

      Vol:
    E88-D No:1
      Page(s):
    31-38

    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.

FlyerIEICE has prepared a flyer regarding multilingual services. Please use the one in your native language.