Keyword Search Result

[Keyword] leaf-size(1hit)

1-1hit
  • On Multi-Inkdot Two-Way Alternating Turing Machines and Pushdown Automata with Sublogarithmic Space and Constant Leaf-Size

    Jianliang XU  Katsushi INOUE  Yue WANG  Akira ITO  

     
    LETTER-Automata,Languages and Theory of Computing

      Vol:
    E80-D No:1
      Page(s):
    86-90

    This paper investigates the accepting powers of multi-inkdot two-way alternating pushdown automata (Turing machines) with sublogarithmic space and constant leaf-size. For each k1, and each m0, let weak-ASPACEm [L(n),k] denote the class of languages accepted by simultaneously weakly L(n) space-bounded and k leaf-bounded m-inkdot two-way alternating Turing machines, and let strong-2APDAm[L(n),k] denote the class of languages accepted by simultaneously strongly L(n) space-bounded and k leaf-bounded m-inkdot two-way alternating pushdown automata. We show that(1) strong-2APDAm [log log n,k+1]weak-ASPACEm[o(log n),k]φfor each k1 and each m1, and(2) strong-2APDA(m+1) [log log n,k]weak-ASPACEm[o(log n),k]φfor each k1 and each m0.

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