Oxford logo
[FJKW14] V. Forejt, P. JanĨar, S. Kiefer and J. Worrell. Language equivalence of probabilistic pushdown automata. Information and Computation, 237, pages 1-11, Elsevier. October 2014. [pdf] [bib]
Downloads:  pdf pdf (316 KB)  bib bib
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.

QAV:

Home

People

Projects

Publications