A NOTE ON REALTIME ONE-WAY SYNCHRONIZED ALTERNATING ONE-COUNTER AUTOMATA

This paper investigates the power of realtime one-way synchronized alternating one-counter automata (1saca (1, real)s), and shows that (1) 1saca(1, real)s are more powerful than real-time one-way nondeterministic multicounter automata, and (2) there exists a language accepted by a 1saca(1, real), but not accepted by any realtime one-way alternating multi-stack-counter automata. As a corollary of (2), we have: for each k greater-than-or-equal-to 1, realtime one-way synchronized alternating k-counter (k-stack-counter) automata are more powerful than realtime one-way alternating k-counter (k-stack-counter) automata. We, finally, show that realtime synchronized alternating finite automata recognize exactly regular sets, i.e., that one counter is more powerful than no counter for realtime synchronized alternating automata.