“accepting”, “rejecting”, and “restarting” states. At the end of the computation, if the automaton enters a restarting state, then all the computation is restarted from the beginning. An automaton with restart can be seen as a restricted sweeping two-way automaton. The overall accepting probability can be simply obtained by making a normalization over the accepting and rejecting probabilities in a single round (see also [@YS13A]).

If an affine automaton is restricted to use only non-negative values as an entry of its transition matrix, then it becomes a probabilistic automaton. As a further restriction, if only 1 and 0 are allowed to be used, then it becomes a deterministic automaton. Thus, any (realtime) AfCA using only 0 and 1 as transition values is a (realtime) deterministic counter automaton (realtime DCA).

All the models mentioned above are realtime models, whose tape head moves to the right at each step. Next, we introduce a one-way model, whose tape head is allowed to move to the right or stay at the same position, but not allowed to move to the left.

A one-way deterministic pushdown automaton (1DPA) $ A $ is a 7-tuple $$A=(S, \Sigma, \Gamma, \delta, s_I, Z_0, S_a),$$ where $ S=\{s_1,\ldots, s_n\} 