Affine counter automata
Masaki Nakanishi, Abuzer Yakaryılmaz · arXiv (Cornell University) · 2017
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 promise problem that can be solved by exact affine counter automata but cannot be solved by deterministic 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 in linear time. Lastly, we show that how a counter helps for affine finite automata by showing that the language $ \mathtt{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.