Sublogarithmic Space-Bounded Multi-Inkdot Alternating Hiring Machines with Only Existential (Universal) States

摘要

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, (ⅰ) multi-inkdot 2ATM's with only existential states and the ones with only universal states are incomparable, (ⅱ) k-inkdot 2ATM's are better than k-inkdot 2ATM's with only existential (universal) states, k ≥ 0, and (ⅲ) the class of sets accepted by multi-inkdot 2ATM's with only existential (universal) states is not closed under complementation.