6
$\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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

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

Your Answer

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

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