5
$\begingroup$

I know that the equivalence problem for deterministic one counter automata is decidable, however does anyone know whether it is decidable for all one counter automata or just the deterministic ones?

Any information would be useful, I don't know if this is an open problem or if it has a solution. If there is a known proof (of either decidability or undecidability) then a reference would be greatly appreciated.

$\endgroup$
4
$\begingroup$

I have no time to check the references in detail, but Ibarra states in http://dx.doi.org/10.1007/BF01744294 that, according to Greibachand Baker and Book, the universe problem (is the language $\Sigma^*$?) for non-deterministic one-counter machines with at most one counter reversal is undecidable.

In addition to this, Ibarra considers even more restricted classes for which this problem is undecidable.

Hence, even a subproblem of equivalence is undecidable for a subclass of non-deterministic one-counter machines.

$\endgroup$
  • 1
    $\begingroup$ Thank you, that answers my question. The equivalence problem for all one-counter automata cannot be decidable. $\endgroup$ – Sam Jones Jun 9 '11 at 15:52

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.