2
$\begingroup$

I'm wondering if anyone can point me to either an algorithm or an undecidability proof for the following question:

Given a non-deterministic reversal-bounded multicounter machine $M$, is there some deterministic reversal-bounded multicounter machine $M'$ such that $L(M) = L(M')$?

For anyone interested, reversal-bounded counter machines are described at length in Oscar Ibarra's Paper about them.

$\endgroup$

1 Answer 1

2
$\begingroup$

I found a similar argument for context-free languages, which can be used here. It is not decidable, since universality for non-deterministic reversal-bounded multicounter machines is undecidable, but becomes decidable for the deterministic version.

Suppose we can decide if $M$ can be determinized, and perform the determinization if it can. Then we can decide if $L(M) = \Sigma^*$ as follows:

If $M$ cannot be determinized, then clearly it is not universal, since there is a deterministic machine accepting $\Sigma^*$. If $M$ can be determinized, then we determinize it and test if it is universal.

This question on CS.SE give the analogous argument for CFL vs. DCFL.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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