This paper investigates the closure properties of multi-inkdot nondeterministic Turing machines with sublogarithmic space. We show that the class of sets accepted by the Turing machines is not closed under concatenation with regular set, Kleene closure, length-preserving homomorphism, and intersection.

This paper investigates the accepting powers of two-way alternating Turing machines (2ATM's) with only existential (universal) states which have inkdots and sublogarithmic space. It is shown that for sublogarithmic space-bounded computations, (i) multi-inkdot 2ATM's with only existential states and the ones with only universal states are incomparable, (ii) k-inkdot 2ATM's are better than k-inkdot 2ATM's with only existential (universal) states, k ≥ 0, and (iii) the class of sets accepted by multi-inkdot 2ATM's with only existential (universal) states is not closed under complementation.

This paper investigates a hierarchical property based on the number of inkdots in the accepting powers of sublogarithmic space-bounded multi-inkdot two-way alternating Turing machines with only universal states. For each k1 and any function L(n), let strong-2UTMk(L(n)) (weak-2UTMk(L(n))) be the class of sets accepted by strongly (weakly) L(n) space-bounded k-inkdot two-way alternating Turing machines with only universal states. We show that for each k1, strong-2UTMk+1(log log n) - weak-2UTMk(o(log n)) Ø.

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.