Note: This is an archvied version of our old webpage. Some links might be broken. The current one can be found here.
I7 Logo
Chair for Foundations of Software Reliability and Theoretical Computer Science
Informatik Logo TUM Logo
Publications - Language equivalence of probabilistic pushdown automata


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.


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:

    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}

PDF (274 kB)