# Deciding whether DCFG is visibly pushdown

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$$?

• 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.
– orlp
Dec 25 '20 at 18:28
• And regardless this immediately shows the problem is at least semi-decidable.
– orlp
Dec 25 '20 at 18:33