7
$\begingroup$

Is the following problem decidable? If so, what's the best algorithm known?

Instance: a deterministic pushdown automaton $A$
Question: Does there exist (i) some partition of the alphabet into push, pop, and level symbols and (ii) a visibly pushdown automaton that recognizes the language accepted by $A$?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Due to the decidability of DPDA equivalence one 'merely' has to show there exist some (no matter how bad) computable function $f(n)$ upper-bounding the sufficient size of a VPDA for $L(A)$ given DPDA $A$ of size $n$, as we can then simply enumerate them. $\endgroup$
    – orlp
    Dec 25 '20 at 18:28
  • $\begingroup$ And regardless this immediately shows the problem is at least semi-decidable. $\endgroup$
    – orlp
    Dec 25 '20 at 18:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.