<p>I have no time to check the references in detail, but Ibarra states in <a href="http://dx.doi.org/10.1007/BF01744294" rel="nofollow">http://dx.doi.org/10.1007/BF01744294</a> that, according to 
<a href="http://portal.acm.org/citation.cfm?id=321503" rel="nofollow">Greibach</a>and <a href="http://dx.doi.org/10.1016/S0022-0000(74)80027-9" rel="nofollow">Baker and Book</a>, the universe problem (is the language $\Sigma^*$?) for non-deterministic one-counter machines with at most one counter reversal is undecidable. </p>

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

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

CC BY-SA 3.0
2011-06-09T15:52:31.407Z
Thank you, that answers my question. The equivalence problem for all one-counter automata cannot be decidable.
Sam Jones
CC BY-SA 3.0
2011-06-09T14:59:27.570Z
2014-02-19T16:37:08.407Z
2014-02-19T16:37:08.407Z
Dominik D. Freydenberger
<p>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?</p>

<p>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.</p>

<reference-request><computability><fl.formal-languages><automata-theory>
Equivalence problem for one-counter automata
Sam Jones
# Equivalence problem for one-counter automata

(Asked by: username_0 on 2011-06-09)

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.

**Tags:** reference-request, computability, fl.formal-languages, automata-theory


---

## 1 answers

### Answer by username_1 on 2011-06-09. Score: 4 | Accepted answer

I have no time to check the references in detail, but Ibarra states in <http://dx.doi.org/10.1007/BF01744294> that, according to
[Greibach](http://portal.acm.org/citation.cfm?id=321503)and [Baker and Book](http://dx.doi.org/10.1016/S0022-0000(74)80027-9), 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.

> **Comments:**
> **username_0**: Thank you, that answers my question. The equivalence problem for all one-counter automata cannot be decidable.  

---

