1
$\begingroup$

It is widely known that emptiness of counter automata is undecidable since two counters are enough to simulate a Turing machine (see the classic book from Hopcroft and Ullman, for example).

However, what happens if we put a bound $k$ on the values stored by the counters? In this restricted model, the counters cannot be incremented more than $k$.

I think this makes the problem decidable, is this correct? And in this case, which is the complexity? Is there any reference about this problem?

$\endgroup$
3
  • $\begingroup$ If the counters are bounded, you can get rid of them by including them as part of the set of states. $\endgroup$ Sep 23 at 18:11
  • $\begingroup$ Yes, this makes it easy to prove membership in PSPACE, I suppose. But what about the hardness? $\endgroup$
    – gigabytes
    Sep 23 at 18:13
  • $\begingroup$ Can you define the model more precisely? $\endgroup$ Sep 23 at 20:41
0
$\begingroup$

If the counters are bounded by $k$, then the number of possible states is finite, so this is a finite-state machine, and emptiness for finite-state machines is decidable. In particular, if there are $c$ counters, each bounded by $k$, then there are $O(k^c)$ states, so emptiness can be tested in $O(k^c)$ time.

Assuming the automaton allows nondeterminism, it is easy to prove that the problem is NP-hard, by a reduction from 3SAT. (Store the value of $x_i$ in the $i$th counter, selecting its value nondeterministically, then scan over the formula, checking each clause to see if it holds.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.