Title: Exact Affine Counter Automata,
Abstract: We introduce an affine generalization of counter automata, and analyze their
ability as well as affine finite automata. Our contributions are as follows. We
show that there is a language that can be recognized by exact realtime affine
counter automata but by neither 1-way deterministic pushdown automata nor
realtime deterministic k-counter automata. We also show that a certain promise
problem, which is conjectured not to be solved by two-way quantum finite
automata in polynomial time, can be solved by Las Vegas affine finite automata.
Lastly, we show that how a counter helps for affine finite automata by showing
that the language MANYTWINS, which is conjectured not to be recognized by
affine, quantum or classical finite state models in polynomial time, can be
recognized by affine counter automata with one-sided bounded-error in realtime.