The word problem distinguishes counter languages

Abstract

Counter automata are more powerful versions of finite-state automata where addition and subtraction operations are permitted on a set of n integer registers, called counters. We show that the word problem of ${\mathbb{Z}}^n$ is accepted by a nondeterministic $m$-counter automaton if and only if $m\ge n$.

8 pages