Some observations on 1-inkdot alternating multi-counter automata with sublinear space
This paper investigates some fundamental properties of 2-way alternating multi-counter automata (2amca's) with only existential (universal) states which have sublinear space and 1 inkdot. It is shown that for any function s(n) greater than or equal to log n such that log s(n) = o(log n), s(n) space-bounded 1-inkdot 2amca's with only existential states are incomparable with the ones with only universal states, and the ones with only existential (universal) states are not closed under complementation.
1-inkdot alternating multi-counter automata 2-way computation sublinear space complexity