Language equivalence of probabilistic pushdown automata.

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F14%3A00080048" target="_blank" >RIV/00216224:14330/14:00080048 - isvavai.cz</a>
Alternative codes found
RIV/61989100:27240/14:86092894
Result on the web
<a href="http://dx.doi.org/10.1016/j.ic.2014.04.003" target="_blank" >http://dx.doi.org/10.1016/j.ic.2014.04.003</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.ic.2014.04.003" target="_blank" >10.1016/j.ic.2014.04.003</a>

Result language
angličtina
Original language name
Language equivalence of probabilistic pushdown automata.
Original language 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 beenopen 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.
Czech name
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
IN - Informatics
OECD FORD branch
—

Project
<a href="/en/project/GAP202%2F11%2F0340" target="_blank" >GAP202/11/0340: Modelling and verification of parallel systems</a><br>
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year
2014
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)