Language equivalence of probabilistic pushdown automata.

• Autoři: FOREJT Vojtěch; JANČAR Petr; KIEFER Stefan; WORRELL James
• Rok publikování: 2014
• Druh: Článek v odborném periodiku
• Časopis / Zdroj: Information and computation
• Fakulta / Pracoviště MU: Fakulta informatiky
• Doi: http://dx.doi.org/10.1016/j.ic.2014.04.003
• Obor: Informatika
• Klíčová slova: Pushdown systems; Language equivalence; Probabilistic systems
• Popis: 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.

Související projekty

• Podpora perspektivních výzkumných týmů Fakulty informatiky a vynikajících vědeckých pracovníků z jiných institucí působících na Fakultě informatiky