Sublogarithmic Space-bounded Multi-inkdot Alternating Pushdown Automata with Only Existential (Universal) States

摘要

This paper investigates some properties of two-way alternating pushdown automata with only existential (universal) states which have inkdots and sublogarithmic space. We show, for example, that for sublogarithmic space-bounded computations, multi-inkdot two-way alternating pushdown automata with only existential states are incomparable with the ones with only universal states, and the classes of sets accepted by these pushdown automata are not closed under complementation.