Language equivalence of probabilistic pushdown automata.
|Year of publication||2014|
|Type||Article in Periodical|
|Magazine / Source||Information and computation|
|MU Faculty or unit|
|Keywords||Pushdown systems; Language equivalence; Probabilistic systems|
|Description||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.|