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.
Equivalence problem for one-counter automata
reference request;computability;fl.formal languages;automata theory
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.