# Is the following extension of finite state automata studied?

Consider a finite state machine as usual, but every transition, it can also update an integer counter by adding or subtracting a number. Say, a transition function of the form $\delta(q,a) = (p,k)$ moves to the new state $p$, and add $k$ to the counter, where $k \in \mathbb{Z}$ (so $k$ can be positive, negative, or zero).

A string is accepted if the final state and the counter value is in $F$, where $F$ is a finite set of pairs of states and counter values.

Is this model known? I could not find any reference of this particular extension.

• Depends on the possible values of $k$. Can $k$ be negative? Oct 1 '16 at 22:29
• $k$ can be negative. Oct 2 '16 at 3:13
• A related question: cs.stackexchange.com/questions/7574/… Oct 4 '16 at 12:31

Assuming $k$ can be any integer, then this can be formalized as a blind one-counter automaton. Usually these automata accept on final state when its counter is zero, but we can easily model your acceptance type if you allow $\epsilon$ transitions (that do not consume input). If I am not mistaken, like with finite state automata, one can get rid of the $\epsilon$, but that is a non-trivial result.