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

概要

論文の詳細を見る
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 k≧1, and each m≧0, let weak-ASPACE^m[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-2APDA^m[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-2APDA^m[log log n, k+1] - weak-ASPACE^m[o(log n), k] ≠ ∅ for each k≧1 and each m≧1, and (2) strong-2APDA^<(m+1)>[log log n, k] - weak-ASPACE^m[o(log n), k] ≠ ∅ for each k≧1 and each m≧0.
社団法人電子情報通信学会の論文
1997-01-25