Reference:

Vojtěch Forejt, Petr Jančar, Stefan Kiefer, and James Worrell. Language equivalence of probabilistic pushdown automata. Information and Computation, 237:1–11, October 2014.

Abstract:

We study the language equivalence problem for probabilistic pushdown automata (pPDA) and their subclasses. We show that the problem is interreducible with the multiplicity equivalence problem for context-free grammars, the decidability of which has been open for several decades. Interreducibility also holds for pPDA with one control state. In contrast, for the case of a one-letter input alphabet we show that pPDA language equivalence (and hence multiplicity equivalence of context-free grammars) is in PSPACE and at least as hard as the polynomial identity testing problem.

Suggested BibTeX entry:

@article{14FJKW-IC,
    author = {Vojt\v{e}ch Forejt and Petr Jan\v{c}ar and Stefan Kiefer and James Worrell},
    journal = {Information and Computation},
    month = {October},
    pages = {1--11},
    title = {Language equivalence of probabilistic pushdown automata},
    volume = {237},
    year = {2014}
}