A Note on Non-Closure Property of Sublogarithmic Space-Bounded 1-Inkdot Alternating Pushdown Automata with Only Existential (Universal) States

1-inkdot alternating pushdown automaton is a slightly modified alternating pushdown automaton with the additional power of marking at most 1 tape-cell on the input (with an inkdot) once. This paper investigates the closure property of sublogarithmic space-bounded 1-inkdot alternating pushdown automata with only existential (universal) states, and shows, for example, that for any function L(n) such that L(n) ≥ log log nn and L(n) = o(log n), the class of sets accepted by weakly (strongly) L(n) space-bounded 1-inkdot two-way alternating pushdown automata with only existential (universal) states is not closed under concatenation with regular sets, length-preserving homomorphism, and Kleene closure. This work is supported by the National Natural Science Foundation of China under Grant No. 60403012.