A note on realtime one-way alternating and deterministic multi-counter automata
This paper investigates the accepting powers of one-way alternating and deterministic multi-counter automata operating in realtime. We partially solve the open problem posed in [4], and show that for each k greater than or equal to 1. there is a language accepted by a realtune one-way deterministic (k + 3)-counter automaton, but not accepted by any realtime one-way alternating k-counter automaton.
deterministic multi-counter automata alternating multi-counter automata one-way computation realtime computation computational complexity