simpler setups for the tasks done by QCAs.

Our main contribution in this paper is that we show that there is a language that can be recognized exactly (zero-error) by realtime AfCAs but neither by 1-way deterministic pushdown automata nor by realtime deterministic $k$-counter automata. This is the first separation result concerning AfCAs. This is a strong result since an exact one-way probabilistic one-counter automaton (PCA) is simply a one-way deterministic one-counter automaton (DCA) and it is still open whether exact one-way QCAs are more powerful than one-way DCAs and whether bounded-error one-way QCAs are more powerful than one-way bounded-error PCAs (see [@SY12A; @NY15A] for some affirmative results).

In [@RasY14A], it was shown that a certain promise problem can be solved by two-way QFAs (2QCFAs) exactly but in exponential time, and bounded-error two-way PFAs (2PFAs) can solve the problem only if they are allowed to use logarithmic amount of memory. We show that the same problem can be solved by realtime Las Vegas AfAs or AfAs with restart in linear expected time. Lastly, we address the language $ {\mathtt{MANYTWINS}}$, which is conjectured not to be recognized by affine, quantum or classical finite state models in polynomial time. We show how 