Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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.
