← All problems
Unverified
Language Equivalence between Nondeterministic and Deterministic One-Counter Machines
Problem A: Given a deterministic one-counter automaton (a pushdown automaton with one stack alphabet) and a nondeterministic one-counter net (a one-counter automaton with no zero-tests) , decide if the language recognised by is the same as the language recognised by . Decidability of A is open. This is related to the open question of decidability for the following problem, which is relatively more well-known. Problem B: Given a deterministic one-counter net and a nondeterministic one-counter net , decide if the language recognised by is the same as the language recognised by .
