Language equivalence of probabilistic pushdown automata.

Kód výsledku v 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>

Nalezeny alternativní kódy

RIV/61989100:27240/14:86092894

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Language equivalence of probabilistic pushdown automata.

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Language equivalence of probabilistic pushdown automata.

Popis výsledku anglicky

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.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GAP202%2F11%2F0340" target="_blank" >GAP202/11/0340: Modelování a verifikace paralelních systémů</a><br>

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2014

Kód důvěrnosti údajů

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

Název periodika

Information and computation

ISSN

0890-5401

e-ISSN

—

Svazek periodika

237

Číslo periodika v rámci svazku

October 2014

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

11

Strana od-do

1-11

Kód UT WoS článku

000339468300001

EID výsledku v databázi Scopus

—