← 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) AA and a nondeterministic one-counter net (a one-counter automaton with no zero-tests) NN, decide if the language recognised by AA is the same as the language recognised by NN. 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 DD and a nondeterministic one-counter net NN, decide if the language recognised by DD is the same as the language recognised by NN.

Coming soon

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li
Hongwei Hu portraitHongwei Hu