Publication details
Language equivalence of probabilistic pushdown automata.
| Authors | |
|---|---|
| Year of publication | 2014 |
| Type | Article in Periodical |
| Magazine / Source | Information and computation |
| MU Faculty or unit | |
| Citation | |
| Doi | https://doi.org/10.1016/j.ic.2014.04.003 |
| Field | Informatics |
| 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. |
| Related projects: |